oj.uz

답안 #336253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336253 2020-12-15T03:30:00 Z beksultan04 Bigger segments (IZhO19_segments) C++14
13 / 100
 1500 ms 112720 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
const int N = 2e6+11,INF=1e9+7;
int q[N],ct[N],der[4*N],ans,n,h1[N],h2[N],h3[N],h4[N],dp[N];
vector <pii > v[N];
int rec(int j,int sum,int cnt){
    int i;
    if (j > n){
        ret cnt;
    }

    int x1 = j+(sum*37)%N;
    x1%=N;

    int x2 = j+(sum*31)%N;
    x2%=N;

    int x3 = j+(sum*41)%N;
    x3%=N;

    int x4 = j*57+(sum*57*57)%N;
    x4%=N;


    if (h1[x1] == h2[x2] && h2[x2]==h3[x3] && h4[x4]==h3[x3] && h1[x1] == 1){
        ret dp[j];
    }
    h1[x1] = h2[x2] =h3[x3] = h4[x4] = 1;
    int mx=0;
    for (i=0;i<v[j].size();++i){
        if (v[j][i].fr >= sum){
            mx = max(mx,rec(v[j][i].sc+1,v[j][i].fr,cnt+1));
        }
    }
    ret dp[j]=max(mx,dp[j]);

}
main(){
    int i,j;
    scan1(n)
    for (i=0;i<N;++i)h1[i]=h2[i]=h3[i]=-1;
    for (i=1;i<=n;++i){
        scan1(q[i])
    }
    for (i=1;i<=n;++i){
        int sum=0;
        for (j=i;j<=n;++j){
            sum+=q[j];
            v[i].pb({sum,j});
        }
    }

    cout <<rec(1,0,0);;
}

Compilation message

segments.cpp: In function 'long long int rec(long long int, long long int, long long int)':
segments.cpp:43:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (i=0;i<v[j].size();++i){
      |              ~^~~~~~~~~~~~
segments.cpp: At global scope:
segments.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      |      ^
segments.cpp: In function 'int main()':
segments.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define scan1(a) scanf("%lld",&a);
      |                  ~~~~~^~~~~~~~~~~
segments.cpp:53:5: note: in expansion of macro 'scan1'
   53 |     scan1(n)
      |     ^~~~~
segments.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define scan1(a) scanf("%lld",&a);
      |                  ~~~~~^~~~~~~~~~~
segments.cpp:56:9: note: in expansion of macro 'scan1'
   56 |         scan1(q[i])
      |         ^~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 94316 KB Output is correct
2 Correct 57 ms 94316 KB Output is correct
3 Correct 57 ms 94316 KB Output is correct
4 Correct 52 ms 94444 KB Output is correct
5 Correct 57 ms 94444 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct
7 Correct 66 ms 94572 KB Output is correct
8 Correct 60 ms 94444 KB Output is correct
9 Correct 60 ms 94572 KB Output is correct
10 Correct 55 ms 94956 KB Output is correct
11 Correct 62 ms 94700 KB Output is correct
12 Correct 60 ms 94444 KB Output is correct
13 Correct 56 ms 94700 KB Output is correct
14 Correct 58 ms 94828 KB Output is correct
15 Correct 59 ms 94828 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 94316 KB Output is correct
2 Correct 57 ms 94316 KB Output is correct
3 Correct 57 ms 94316 KB Output is correct
4 Correct 52 ms 94444 KB Output is correct
5 Correct 57 ms 94444 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct
7 Correct 66 ms 94572 KB Output is correct
8 Correct 60 ms 94444 KB Output is correct
9 Correct 60 ms 94572 KB Output is correct
10 Correct 55 ms 94956 KB Output is correct
11 Correct 62 ms 94700 KB Output is correct
12 Correct 60 ms 94444 KB Output is correct
13 Correct 56 ms 94700 KB Output is correct
14 Correct 58 ms 94828 KB Output is correct
15 Correct 59 ms 94828 KB Output is correct
16 Correct 62 ms 98924 KB Output is correct
17 Correct 1106 ms 112720 KB Output is correct
18 Execution timed out 1554 ms 112580 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 94316 KB Output is correct
2 Correct 57 ms 94316 KB Output is correct
3 Correct 57 ms 94316 KB Output is correct
4 Correct 52 ms 94444 KB Output is correct
5 Correct 57 ms 94444 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct
7 Correct 66 ms 94572 KB Output is correct
8 Correct 60 ms 94444 KB Output is correct
9 Correct 60 ms 94572 KB Output is correct
10 Correct 55 ms 94956 KB Output is correct
11 Correct 62 ms 94700 KB Output is correct
12 Correct 60 ms 94444 KB Output is correct
13 Correct 56 ms 94700 KB Output is correct
14 Correct 58 ms 94828 KB Output is correct
15 Correct 59 ms 94828 KB Output is correct
16 Correct 62 ms 98924 KB Output is correct
17 Correct 1106 ms 112720 KB Output is correct
18 Execution timed out 1554 ms 112580 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 94316 KB Output is correct
2 Correct 57 ms 94316 KB Output is correct
3 Correct 57 ms 94316 KB Output is correct
4 Correct 52 ms 94444 KB Output is correct
5 Correct 57 ms 94444 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct
7 Correct 66 ms 94572 KB Output is correct
8 Correct 60 ms 94444 KB Output is correct
9 Correct 60 ms 94572 KB Output is correct
10 Correct 55 ms 94956 KB Output is correct
11 Correct 62 ms 94700 KB Output is correct
12 Correct 60 ms 94444 KB Output is correct
13 Correct 56 ms 94700 KB Output is correct
14 Correct 58 ms 94828 KB Output is correct
15 Correct 59 ms 94828 KB Output is correct
16 Correct 62 ms 98924 KB Output is correct
17 Correct 1106 ms 112720 KB Output is correct
18 Execution timed out 1554 ms 112580 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 94316 KB Output is correct
2 Correct 57 ms 94316 KB Output is correct
3 Correct 57 ms 94316 KB Output is correct
4 Correct 52 ms 94444 KB Output is correct
5 Correct 57 ms 94444 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct
7 Correct 66 ms 94572 KB Output is correct
8 Correct 60 ms 94444 KB Output is correct
9 Correct 60 ms 94572 KB Output is correct
10 Correct 55 ms 94956 KB Output is correct
11 Correct 62 ms 94700 KB Output is correct
12 Correct 60 ms 94444 KB Output is correct
13 Correct 56 ms 94700 KB Output is correct
14 Correct 58 ms 94828 KB Output is correct
15 Correct 59 ms 94828 KB Output is correct
16 Correct 62 ms 98924 KB Output is correct
17 Correct 1106 ms 112720 KB Output is correct
18 Execution timed out 1554 ms 112580 KB Time limit exceeded
19 Halted 0 ms 0 KB -