답안 #1022797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022797	2024-07-14T05:21:55 Z	vjudge1	메기 농장 (IOI22_fish)	C++17	20 / 100	279 ms	116208 KB

fish

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

const int maxn = 1e5 + 100;
const int maxl = 11;
int n;
ll dp[maxn][maxl][maxl];
ll a[maxn][maxl];
ll pref[2][maxn];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N;
    if(*max_element(X.begin(), X.end()) <= 1 && n > 2){
        for(int i = 0; i < M; i++){
            Y[i]++;
            pref[X[i]][Y[i]] += W[i];
        }
        for(int i = 1; i <= n; i++){
            pref[0][i] += pref[0][i-1];
        }
        for(int i = n; i > 0; i--){
            pref[1][i] += pref[1][i+1];
        }
        ll ans = 0;
        for(int i = 0; i <= n; i++){
            ans = max(ans, pref[0][i] + pref[1][i+1]);
        }
        return ans;
    }
    bool ok = 1;
    ll sum = 0;
    for(int i = 0; i < M; i++){
        X[i]++; Y[i]++;
        if(Y[i] <= 11){
            a[X[i]][Y[i]] += W[i];
        }
        ok &= Y[i] & 1;
        sum += W[i];
    }
    if(ok) return sum;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 10; j++){
            a[i][j] += a[i][j-1];
        }
    }
    for(int c = 1; c <= n + 1; c++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
                dp[c][i][j] = -(ll)1e18;
                if(c == 1 && i == 0) dp[c][i][j] = 0;
            }
        }
    }
    for(int c = 2; c <= n + 1; c++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
                for(int k = 0; k <= 10; k++){
                    ll x = dp[c-1][i][j];
                    if(max(i, k) > j){
                        x += a[c-1][max(i, k)] - a[c-1][j];
                    }
                    dp[c][j][k] = max(dp[c][j][k], x);
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 10; i++){
        ans = max(ans, dp[n+1][i][0]);
    }
    return ans;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	4956 KB	Output is correct
2	Correct	38 ms	5972 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Incorrect	279 ms	116208 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '16175729136'
6	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	30 ms	8224 KB	Output is correct
3	Correct	44 ms	9820 KB	Output is correct
4	Correct	30 ms	5096 KB	Output is correct
5	Correct	29 ms	5920 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	440 KB	Output is correct
10	Correct	2 ms	1884 KB	Output is correct
11	Correct	1 ms	1824 KB	Output is correct
12	Correct	34 ms	4948 KB	Output is correct
13	Correct	19 ms	5968 KB	Output is correct
14	Correct	17 ms	4956 KB	Output is correct
15	Correct	36 ms	5076 KB	Output is correct
16	Correct	16 ms	4696 KB	Output is correct
17	Correct	20 ms	5208 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1884 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	13 ms	7768 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	448 KB	Output is correct
10	Correct	2 ms	868 KB	Output is correct
11	Correct	1 ms	608 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	1 ms	352 KB	Output is correct
14	Correct	2 ms	608 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	448 KB	Output is correct
10	Correct	2 ms	868 KB	Output is correct
11	Correct	1 ms	608 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	1 ms	352 KB	Output is correct
14	Correct	2 ms	608 KB	Output is correct
15	Incorrect	2 ms	604 KB	1st lines differ - on the 1st token, expected: '299', found: '10'
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	448 KB	Output is correct
10	Correct	2 ms	868 KB	Output is correct
11	Correct	1 ms	608 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	1 ms	352 KB	Output is correct
14	Correct	2 ms	608 KB	Output is correct
15	Incorrect	2 ms	604 KB	1st lines differ - on the 1st token, expected: '299', found: '10'
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1884 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	13 ms	7768 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	4956 KB	Output is correct
2	Correct	38 ms	5972 KB	Output is correct
3	Correct	1 ms	1884 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Incorrect	279 ms	116208 KB	1st lines differ - on the 1st token, expected: '149814460735479', found: '16175729136'
6	Halted	0 ms	0 KB	-

답안 #1022797

Compilation message