Submission #871668

#TimeUsernameProblemLanguageResultExecution timeMemory
871668vjudge1Difference (POI11_roz)C++17
100 / 100
756 ms26088 KiB
#include "bits/stdc++.h" #define ii pair <int, int> #define F first #define S second using namespace std; const int N = 1e6+5; int n; char a[N]; int pre[N]; vector <int> save[30]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; save[a[i]-'a'].push_back(i); } int res = 0; for (int c1 = 0 ; c1 < 26 ; c1++) for (int c2 = 0 ; c2 < 26 ; c2++) { if (c1 == c2) continue; vector <ii> pos; pos.push_back(ii(0, 0)); int pos1 = 0, pos2 = 0; while(pos1 < save[c1].size() || pos2 < save[c2].size()) { if (pos1 == save[c1].size()) { pos.push_back(ii(save[c2][pos2], -1)); pos2++; continue; } if (pos2 == save[c2].size()) { pos.push_back(ii(save[c1][pos1], 1)); pos1++; continue; } if (save[c1][pos1] < save[c2][pos2]) { pos.push_back(ii(save[c1][pos1], 1)); pos1++; } else { pos.push_back(ii(save[c2][pos2], -1)); pos2++; } } int cur = 0, last = 0; for (int i = 1 ; i < pos.size() ; i++) { cur += pos[i].S; if (pos[i].S == -1) last = i; if (last) res = max(res, cur-pre[last-1]); pre[i] = min(cur, pre[i-1]); } } cout << res; return 0; }

Compilation message (stderr)

roz.cpp: In function 'int main()':
roz.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             while(pos1 < save[c1].size() || pos2 < save[c2].size()) {
      |                   ~~~~~^~~~~~~~~~~~~~~~~
roz.cpp:27:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             while(pos1 < save[c1].size() || pos2 < save[c2].size()) {
      |                                             ~~~~~^~~~~~~~~~~~~~~~~
roz.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |                 if (pos1 == save[c1].size()) {
      |                     ~~~~~^~~~~~~~~~~~~~~~~~
roz.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 if (pos2 == save[c2].size()) {
      |                     ~~~~~^~~~~~~~~~~~~~~~~~
roz.cpp:48:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int i = 1 ; i < pos.size() ; i++) {
      |                              ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...