oj.uz

Submission #500954

# Submission time Handle Problem Language Result Execution time Memory
500954 2022-01-01T18:08:54 Z Mounir Difference (POI11_roz) C++14
10 / 100
 1000 ms 17608 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define x first
#define y second
#define int long long
using namespace std;

signed main(){
      int nVals; cin >> nVals;
      string line; cin >> line;

      vector<int> posis[26];
      for (int i = 0; i < nVals; ++i)
            posis[line[i] - 'a'].pb(i);
      
      int maxi = 0;
      int pt = 0;
      for (int i = 0; i < nVals;){
            pt = i;
            while (pt < nVals && line[pt] == line[i])
                  ++pt;
            chmax(maxi, pt - i);
            i = pt;
      }

      for (int iMin = 0; iMin < 26; ++iMin)
            for (int iMax = 0; iMax < 6; ++iMax){
                  if (posis[iMin].empty() || posis[iMax].empty()) continue;
                  vector<pii> vals;
                  for (int posi : posis[iMin])
                        vals.pb({posi, -1});
                  for (int posi : posis[iMax])
                        vals.pb({posi, 1});
                  sort(all(vals));
                  vector<pii> tmp;
                  tmp.pb(vals[0]);
                  for (int i = 1; i < sz(vals); ++i){
                        if (vals[i].y == vals[i - 1].y)
                              tmp[sz(tmp) - 1].y += vals[i].y;
                        else
                              tmp.pb(vals[i]);
                  }
                  vals = tmp;

                  int pMin = 0, pMax = 0, p[sz(vals)];
                  int id = 0, pCur = 0;
                  for (pii val : vals){
                        pCur += val.second;
                        p[id] = pCur;

                        if (id != 0){
                              chmax(maxi, abs(pCur - pMin));
                              chmax(maxi, abs(pMax - pCur));
                        
                              chmin(pMin, p[id - 1]);
                              chmax(pMax, p[id - 1]);
                        }
                        id++;
                  }
            }
      cout << maxi << endl;
      return 0;   
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 1740 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 17608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 17580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 17156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 17600 KB Time limit exceeded
2 Halted 0 ms 0 KB -