답안 #671286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671286	2022-12-12T18:30:17 Z	tbzard	메기 농장 (IOI22_fish)	C++17	52 / 100	1000 ms	260384 KB

fish

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

ll dp[3005][3005][3]; // A(a), (A)a, (A)
ll pref[2][3005];
int pos[3005][3005];
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for(int i=0;i<sz(x);i++) pos[x[i]+1][y[i]+1] = w[i];
    memset(dp, -1, sizeof(dp));

    ll ans = 0;
    for(int i=1;i<=n;i++){
        memset(pref, 0, sizeof(pref));
        for(int j=1;j<=n;j++){
            pref[0][j] = pref[0][j-1] + pos[i-1][j];
            pref[1][j] = pref[1][j-1] + pos[i][j];
        }
        if(i == 1){
            for(int j=0;j<=n;j++) dp[i][j][2] = 0;
        }
        else{
            // 0
            ll mx = -1e18;
            for(int j=n;j>=0;j--){
                if(dp[i-1][j][0] != -1) mx = max(mx, dp[i-1][j][0] + pref[1][j]);
                if(dp[i-1][j][2] != -1) mx = max(mx, dp[i-1][j][2] + pref[1][j]);
                dp[i][j][0] = max(dp[i][j][0], mx - pref[1][j]);
            }

            // 1
            for(int j=n;j>=0;j--){
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0] + pref[1][j]);
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][2] + pref[1][j]);
            }


            // 2
            ll mx0 = -1e18, mx1 = -1e18;
            for(int j=0;j<=n;j++){
                if(dp[i-1][j][0] != -1) mx0 = max(mx0, dp[i-1][j][0]);
                if(dp[i-1][j][1] != -1) mx1 = max(mx1, dp[i-1][j][1] - pref[0][j]);
                if(dp[i-1][j][2] != -1) mx1 = max(mx1, dp[i-1][j][2] - pref[0][j]);
                dp[i][j][2] = max(dp[i][j][2], mx0);
                dp[i][j][2] = max(dp[i][j][2], mx1 + pref[0][j]);
            }
        }

        ll sum = 0;
        for(int j=0;j<=n;j++){
            sum += pos[i+1][j];
            ans = max(ans, dp[i][j][0] + sum);
            ans = max(ans, dp[i][j][2] + sum);
        }
    }

    return ans;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1090 ms	214920 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	212384 KB	Output is correct
2	Execution timed out	1098 ms	216720 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1094 ms	212536 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	212304 KB	Output is correct
2	Correct	80 ms	212300 KB	Output is correct
3	Correct	80 ms	212308 KB	Output is correct
4	Correct	81 ms	212300 KB	Output is correct
5	Correct	87 ms	212328 KB	Output is correct
6	Correct	80 ms	212356 KB	Output is correct
7	Correct	79 ms	212460 KB	Output is correct
8	Correct	79 ms	212348 KB	Output is correct
9	Correct	80 ms	212920 KB	Output is correct
10	Correct	111 ms	213712 KB	Output is correct
11	Correct	81 ms	212984 KB	Output is correct
12	Correct	86 ms	213556 KB	Output is correct
13	Correct	82 ms	212664 KB	Output is correct
14	Correct	83 ms	213532 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	212304 KB	Output is correct
2	Correct	80 ms	212300 KB	Output is correct
3	Correct	80 ms	212308 KB	Output is correct
4	Correct	81 ms	212300 KB	Output is correct
5	Correct	87 ms	212328 KB	Output is correct
6	Correct	80 ms	212356 KB	Output is correct
7	Correct	79 ms	212460 KB	Output is correct
8	Correct	79 ms	212348 KB	Output is correct
9	Correct	80 ms	212920 KB	Output is correct
10	Correct	111 ms	213712 KB	Output is correct
11	Correct	81 ms	212984 KB	Output is correct
12	Correct	86 ms	213556 KB	Output is correct
13	Correct	82 ms	212664 KB	Output is correct
14	Correct	83 ms	213532 KB	Output is correct
15	Correct	87 ms	213620 KB	Output is correct
16	Correct	84 ms	212532 KB	Output is correct
17	Correct	95 ms	215244 KB	Output is correct
18	Correct	93 ms	214968 KB	Output is correct
19	Correct	93 ms	215600 KB	Output is correct
20	Correct	97 ms	215596 KB	Output is correct
21	Correct	92 ms	215580 KB	Output is correct
22	Correct	105 ms	217540 KB	Output is correct
23	Correct	86 ms	214256 KB	Output is correct
24	Correct	90 ms	215068 KB	Output is correct
25	Correct	83 ms	213548 KB	Output is correct
26	Correct	84 ms	214068 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	212304 KB	Output is correct
2	Correct	80 ms	212300 KB	Output is correct
3	Correct	80 ms	212308 KB	Output is correct
4	Correct	81 ms	212300 KB	Output is correct
5	Correct	87 ms	212328 KB	Output is correct
6	Correct	80 ms	212356 KB	Output is correct
7	Correct	79 ms	212460 KB	Output is correct
8	Correct	79 ms	212348 KB	Output is correct
9	Correct	80 ms	212920 KB	Output is correct
10	Correct	111 ms	213712 KB	Output is correct
11	Correct	81 ms	212984 KB	Output is correct
12	Correct	86 ms	213556 KB	Output is correct
13	Correct	82 ms	212664 KB	Output is correct
14	Correct	83 ms	213532 KB	Output is correct
15	Correct	87 ms	213620 KB	Output is correct
16	Correct	84 ms	212532 KB	Output is correct
17	Correct	95 ms	215244 KB	Output is correct
18	Correct	93 ms	214968 KB	Output is correct
19	Correct	93 ms	215600 KB	Output is correct
20	Correct	97 ms	215596 KB	Output is correct
21	Correct	92 ms	215580 KB	Output is correct
22	Correct	105 ms	217540 KB	Output is correct
23	Correct	86 ms	214256 KB	Output is correct
24	Correct	90 ms	215068 KB	Output is correct
25	Correct	83 ms	213548 KB	Output is correct
26	Correct	84 ms	214068 KB	Output is correct
27	Correct	180 ms	224568 KB	Output is correct
28	Correct	151 ms	223628 KB	Output is correct
29	Correct	269 ms	226680 KB	Output is correct
30	Correct	274 ms	253716 KB	Output is correct
31	Correct	267 ms	254448 KB	Output is correct
32	Correct	166 ms	227884 KB	Output is correct
33	Correct	268 ms	260328 KB	Output is correct
34	Correct	278 ms	260384 KB	Output is correct
35	Correct	212 ms	230636 KB	Output is correct
36	Correct	269 ms	235340 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1094 ms	212536 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1090 ms	214920 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #671286

Compilation message