Submission #58391

#	Time	Username	Problem	Language	Result	Execution time	Memory
58391		jaeyong0201	구간 성분 (KOI15_interval)	C++17	100 / 100	759 ms	47596 KiB

interval

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39