oj.uz

Submission #58391

# Submission time Handle Problem Language Result Execution time Memory
58391 2018-07-17T16:24:53 Z jaeyong0201 구간 성분 (KOI15_interval) C++17
100 / 100
 759 ms 47596 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long p[1510][1510], q[1510][1510];
hash<string> h;
vector<pair<long long, int>> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string a, b;
    int ans = 0;
    cin>>a>>b;
    for(int i=0; i<a.size(); i++) {
        p[i][i] = h.operator()(string(1, a[i]));
        v.push_back({p[i][i], 1});
    }
    for(int i=1; i<a.size(); i++) {
        for(int j=0; j<a.size()-i; j++) {
            p[j][i+j] = p[j][i+j-1] + p[i+j][i+j];
            v.push_back({p[j][i+j], i+1});
        }
    }
    sort(v.begin(), v.end());
    for(int i=0; i<b.size(); i++) {
        q[i][i] = h.operator()(string(1, b[i]));
        if(binary_search(v.begin(), v.end(), make_pair(q[i][i], 1))) {
            ans = max(ans, 1);
        }
    }
    for(int i=1; i<b.size(); i++) {
        for(int j=0; j<b.size()-i; j++) {
            q[j][i+j] = q[j][i+j-1] + q[i+j][i+j];
            if(binary_search(v.begin(), v.end(), make_pair(q[j][i+j], i+1))) {
                ans = max(ans, i+1);
            }
        }
    }
    cout << ans;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
interval.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<a.size(); i++) {
                  ~^~~~~~~~~
interval.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size()-i; j++) {
                      ~^~~~~~~~~~~
interval.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<b.size(); i++) {
                  ~^~~~~~~~~
interval.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<b.size(); i++) {
                  ~^~~~~~~~~
interval.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<b.size()-i; j++) {
                      ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 908 KB Output is correct
3 Correct 4 ms 1460 KB Output is correct
4 Correct 4 ms 1484 KB Output is correct
5 Correct 5 ms 1488 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7108 KB Output is correct
2 Correct 46 ms 7924 KB Output is correct
3 Correct 32 ms 8600 KB Output is correct
4 Correct 22 ms 8660 KB Output is correct
5 Correct 49 ms 8660 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 24412 KB Output is correct
2 Correct 269 ms 24412 KB Output is correct
3 Correct 335 ms 24428 KB Output is correct
4 Correct 265 ms 24428 KB Output is correct
5 Correct 262 ms 24428 KB Output is correct
6 Correct 272 ms 24584 KB Output is correct
7 Correct 343 ms 24584 KB Output is correct
8 Correct 315 ms 24584 KB Output is correct
9 Correct 305 ms 24584 KB Output is correct
10 Correct 292 ms 24584 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 32680 KB Output is correct
2 Correct 681 ms 47592 KB Output is correct
3 Correct 759 ms 47592 KB Output is correct
4 Correct 566 ms 47596 KB Output is correct
5 Correct 738 ms 47596 KB Output is correct