fork download
copy 
  1. // Bài 5
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const __int128 INF = ((__int128)1 << 120);
  7.  
  8. const int BUF_SIZE = 1 << 20;
  9. char buf[BUF_SIZE];
  10. int buf_ptr = 0, buf_len = 0;
  11.  
  12. inline char getChar() {
  13.     if (buf_ptr >= buf_len) {
  14.         buf_ptr = 0;
  15.         buf_len = fread(buf, 1, BUF_SIZE, stdin);
  16.         if (buf_len == 0) return EOF;
  17.     }
  18.     return buf[buf_ptr++];
  19. }
  20.  
  21. inline int readInt() {
  22.     int x = 0;
  23.     char c = getChar();
  24.     while (c < '0' || c > '9') {
  25.         if (c == EOF) return 0;
  26.         c = getChar();
  27.     }
  28.     while (c >= '0' && c <= '9') {
  29.         x = x * 10 + (c - '0');
  30.         c = getChar();
  31.     }
  32.     return x;
  33. }
  34.  
  35. inline long long readLong() {
  36.     long long x = 0;
  37.     bool neg = false;
  38.     char c = getChar();
  39.     while (c < '0' || c > '9') {
  40.         if (c == '-') neg = true;
  41.         if (c == EOF) return 0;
  42.         c = getChar();
  43.     }
  44.     while (c >= '0' && c <= '9') {
  45.         x = x * 10 + (c - '0');
  46.         c = getChar();
  47.     }
  48.     return neg ? -x : x;
  49. }
  50.  
  51. const uint32_t TABLE_SIZE = 1 << 23; 
  52. const uint64_t EMPTY = 0x7FFFFFFF7FFFFFFFULL; 
  53.  
  54. inline uint32_t hash_f(int d1, int d2) {
  55.     uint64_t x = ((uint64_t)(uint32_t)d1 << 32) | (uint32_t)d2;
  56.     x ^= x >> 30;
  57.     x *= 0xbf58476d1ce4e5b9ULL;
  58.     x ^= x >> 27;
  59.     x *= 0x94d049bb133111ebULL;
  60.     x ^= x >> 31;
  61.     return x & (TABLE_SIZE - 1);
  62. }
  63.  
  64. void print128(__int128 n) {
  65.     if (n < 0) {
  66.         cout << "-";
  67.         n = -n;
  68.     }
  69.     if (n > 9) print128(n / 10);
  70.     cout << (int)(n % 10);
  71. }
  72.  
  73. int main() {
  74.     freopen("thatthach.inp","r",stdin);
  75.     freopen("thatthach.out","w",stdout);
  76.     ios_base::sync_with_stdio(false);
  77.     cin.tie(NULL);
  78.  
  79.     int n = readInt();
  80.     if (n == 0) return 0;
  81.  
  82.     vector<uint8_t> t(n);
  83.     for (int i = 0; i < n; ++i) {
  84.         t[i] = (uint8_t)readInt();
  85.     }
  86.  
  87.     vector<uint64_t> hash_key(TABLE_SIZE, EMPTY);
  88.     vector<__int128> hash_sum(TABLE_SIZE);
  89.  
  90.     __int128 max_val = -INF;
  91.     bool found = false;
  92.  
  93.     uint32_t h = hash_f(0, 0);
  94.     hash_key[h] = 0; // Key tương ứng với d1=0, d2=0
  95.     hash_sum[h] = 0;
  96.  
  97.     int cntA = 0, cntB = 0, cntC = 0;
  98.     __int128 current_s = 0;
  99.  
  100.     for (int i = 0; i < n; ++i) {
  101.         long long val_a = readLong();
  102.  
  103.         if (t[i] == 0) cntA++;
  104.         else if (t[i] == 1) cntB++;
  105.         else if (t[i] == 2) cntC++;
  106.  
  107.         current_s += val_a;
  108.  
  109.         int d1 = cntB - cntA;
  110.         int d2 = cntC - cntB;
  111.         uint64_t cur_key = ((uint64_t)(uint32_t)d1 << 32) | (uint32_t)d2;
  112.  
  113.         uint32_t curr_h = hash_f(d1, d2);
  114.         while (hash_key[curr_h] != EMPTY) {
  115.             if (hash_key[curr_h] == cur_key) {
  116.                 __int128 potential_sum = current_s - hash_sum[curr_h];
  117.                 if (potential_sum > max_val) {
  118.                     max_val = potential_sum;
  119.                 }
  120.                 found = true;
  121.  
  122.                 if (current_s < hash_sum[curr_h]) {
  123.                     hash_sum[curr_h] = current_s;
  124.                 }
  125.                 break;
  126.             }
  127.             curr_h = (curr_h + 1) & (TABLE_SIZE - 1);
  128.         }
  129.  
  130.         if (hash_key[curr_h] == EMPTY) {
  131.             hash_key[curr_h] = cur_key;
  132.             hash_sum[curr_h] = current_s;
  133.         }
  134.     }
  135.  
  136.  
  137.     if (found) {
  138.         print128(max_val);
  139.         cout << "\n";
  140.     } else {
  141.         cout << "KHONG\n";
  142.     }
  143.  
  144.     return 0;
  145. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4dFwBH
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!