답안 #838173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838173	2023-08-26T09:56:39 Z	Dremix10	송신탑 (IOI22_towers)	C++17	11 / 100	757 ms	2097152 KB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define pv(x) {}
#endif

vector<int> arr;
int n,k;

void init(int N, vector<int> H) {
    n = N;
    arr = H;

    int i;
    
}

int max_towers(int L, int R, int D) {
    
    vector<vector<int> > dp(n,vector<int>(n,-MOD));
    int i,j;
    for(i=0;i<n;i++){
        dp[i][i] = 1;
    }

    // dp[i][j], max group size from {0,i} with the last chosen being j (j <= i) 
    
    for(i=L+1;i<=R;i++){
        int maxi = -MOD;
        for(j=i-1;j>=L;j--){
            /// transition of not chosing i
            dp[i][j] = max(dp[i][j],dp[i-1][j]);

            /// transition of choosing i:
            /// must find k bt {j+1,i-1} that has conditions

            if(maxi - D >= max(arr[i],arr[j]))
                dp[i][i] = max(dp[i][i],dp[i-1][j] + 1); 
            
            maxi = max(maxi,arr[j]);
        }
        pv(dp[i])
    }

    int ret = 1;

    for(i=0;i<n;i++)ret = max(ret,dp[R][i]);
    return ret;
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:28:9: warning: unused variable 'i' [-Wunused-variable]
   28 |     int i;
      |         ^

Subtask #1
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	757 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	976 KB	Output is correct
2	Correct	8 ms	15952 KB	Output is correct
3	Correct	7 ms	15952 KB	Output is correct
4	Correct	7 ms	15952 KB	Output is correct
5	Correct	7 ms	15952 KB	Output is correct
6	Correct	7 ms	15952 KB	Output is correct
7	Correct	7 ms	15952 KB	Output is correct
8	Correct	7 ms	16044 KB	Output is correct
9	Correct	7 ms	15952 KB	Output is correct
10	Correct	7 ms	15940 KB	Output is correct
11	Correct	7 ms	15952 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	7 ms	15976 KB	Output is correct
14	Correct	7 ms	15952 KB	Output is correct
15	Correct	7 ms	15952 KB	Output is correct
16	Correct	9 ms	15952 KB	Output is correct
17	Correct	7 ms	15980 KB	Output is correct
18	Correct	7 ms	15952 KB	Output is correct
19	Correct	7 ms	15952 KB	Output is correct
20	Correct	11 ms	15952 KB	Output is correct
21	Correct	13 ms	15932 KB	Output is correct
22	Correct	13 ms	16080 KB	Output is correct
23	Correct	9 ms	15952 KB	Output is correct
24	Correct	10 ms	16048 KB	Output is correct
25	Correct	2 ms	3408 KB	Output is correct
26	Correct	10 ms	15952 KB	Output is correct
27	Correct	11 ms	15952 KB	Output is correct
28	Correct	10 ms	15952 KB	Output is correct
29	Correct	10 ms	16000 KB	Output is correct
30	Correct	10 ms	15980 KB	Output is correct
31	Correct	10 ms	15956 KB	Output is correct
32	Correct	9 ms	15952 KB	Output is correct
33	Correct	10 ms	16000 KB	Output is correct
34	Correct	9 ms	15952 KB	Output is correct
35	Correct	10 ms	15952 KB	Output is correct

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	976 KB	Output is correct
2	Correct	8 ms	15952 KB	Output is correct
3	Correct	7 ms	15952 KB	Output is correct
4	Correct	7 ms	15952 KB	Output is correct
5	Correct	7 ms	15952 KB	Output is correct
6	Correct	7 ms	15952 KB	Output is correct
7	Correct	7 ms	15952 KB	Output is correct
8	Correct	7 ms	16044 KB	Output is correct
9	Correct	7 ms	15952 KB	Output is correct
10	Correct	7 ms	15940 KB	Output is correct
11	Correct	7 ms	15952 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	7 ms	15976 KB	Output is correct
14	Correct	7 ms	15952 KB	Output is correct
15	Correct	7 ms	15952 KB	Output is correct
16	Correct	9 ms	15952 KB	Output is correct
17	Correct	7 ms	15980 KB	Output is correct
18	Correct	7 ms	15952 KB	Output is correct
19	Correct	7 ms	15952 KB	Output is correct
20	Correct	11 ms	15952 KB	Output is correct
21	Correct	13 ms	15932 KB	Output is correct
22	Correct	13 ms	16080 KB	Output is correct
23	Correct	9 ms	15952 KB	Output is correct
24	Correct	10 ms	16048 KB	Output is correct
25	Correct	2 ms	3408 KB	Output is correct
26	Correct	10 ms	15952 KB	Output is correct
27	Correct	11 ms	15952 KB	Output is correct
28	Correct	10 ms	15952 KB	Output is correct
29	Correct	10 ms	16000 KB	Output is correct
30	Correct	10 ms	15980 KB	Output is correct
31	Correct	10 ms	15956 KB	Output is correct
32	Correct	9 ms	15952 KB	Output is correct
33	Correct	10 ms	16000 KB	Output is correct
34	Correct	9 ms	15952 KB	Output is correct
35	Correct	10 ms	15952 KB	Output is correct
36	Runtime error	618 ms	2097152 KB	Execution killed with signal 9
37	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	599 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	595 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	976 KB	Output is correct
2	Correct	8 ms	15952 KB	Output is correct
3	Correct	7 ms	15952 KB	Output is correct
4	Correct	7 ms	15952 KB	Output is correct
5	Correct	7 ms	15952 KB	Output is correct
6	Correct	7 ms	15952 KB	Output is correct
7	Correct	7 ms	15952 KB	Output is correct
8	Correct	7 ms	16044 KB	Output is correct
9	Correct	7 ms	15952 KB	Output is correct
10	Correct	7 ms	15940 KB	Output is correct
11	Correct	7 ms	15952 KB	Output is correct
12	Correct	0 ms	208 KB	Output is correct
13	Correct	7 ms	15976 KB	Output is correct
14	Correct	7 ms	15952 KB	Output is correct
15	Correct	7 ms	15952 KB	Output is correct
16	Correct	9 ms	15952 KB	Output is correct
17	Correct	7 ms	15980 KB	Output is correct
18	Correct	7 ms	15952 KB	Output is correct
19	Correct	7 ms	15952 KB	Output is correct
20	Correct	11 ms	15952 KB	Output is correct
21	Correct	13 ms	15932 KB	Output is correct
22	Correct	13 ms	16080 KB	Output is correct
23	Correct	9 ms	15952 KB	Output is correct
24	Correct	10 ms	16048 KB	Output is correct
25	Correct	2 ms	3408 KB	Output is correct
26	Correct	10 ms	15952 KB	Output is correct
27	Correct	11 ms	15952 KB	Output is correct
28	Correct	10 ms	15952 KB	Output is correct
29	Correct	10 ms	16000 KB	Output is correct
30	Correct	10 ms	15980 KB	Output is correct
31	Correct	10 ms	15956 KB	Output is correct
32	Correct	9 ms	15952 KB	Output is correct
33	Correct	10 ms	16000 KB	Output is correct
34	Correct	9 ms	15952 KB	Output is correct
35	Correct	10 ms	15952 KB	Output is correct
36	Runtime error	618 ms	2097152 KB	Execution killed with signal 9
37	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	757 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

답안 #838173

Compilation message

Subtask #1 0 / 4.0

Subtask #2 11.0 / 11.0

Subtask #3 0 / 12.0

Subtask #4 0 / 14.0

Subtask #5 0 / 17.0

Subtask #6 0 / 19.0

Subtask #7 0 / 23.0

Subtask #1
0 / 4.0

Subtask #2
11.0 / 11.0

Subtask #3
0 / 12.0

Subtask #4
0 / 14.0

Subtask #5
0 / 17.0

Subtask #6
0 / 19.0

Subtask #7
0 / 23.0