답안 #950822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950822	2024-03-20T18:19:35 Z	sysia	메기 농장 (IOI22_fish)	C++17	52 / 100	794 ms	2097152 KB

fish

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "fish.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef pair<int, int> T;
const ll oo = 1e18;


void ckmax(ll &a, ll b){
    a = max(a, b);
}

ll max_weights(int n, int m, vector<int>x, vector<int>y, vector<int>w){
    vector pref(n+1, vector<ll>(n+1));
    for (int i = 0; i<m; i++){
        pref[x[i]+1][y[i]+1] = w[i];
    }
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=n; j++){
            pref[i][j] += pref[i][j-1];
        }
    }
    vector dp(n+1, vector<ll>(3, -oo));
    //dp[h][malejacy czy rosnacy][czy ita kolumna zostala ogarnieta]
    dp[0][0] = 0;
    dp[0][1] = 0;
    for (int i = 1; i<=n; i++){
        vector new_dp(n+1, vector<ll>(3, -oo));
        //h = 0
        //1) poprzednia miala dodatnie pole
        for (int h = 1; h <= n; h++){
            new_dp[0][2] = max(new_dp[0][2], max(dp[h][1], dp[h][0]) + pref[i][h]);
        }
        //2) poprzednia byla zerem
        new_dp[0][0] = max(dp[0][2], dp[0][0]);
        //h > 0
        //1) poprzednia byla pusta
        for (int h = 1; h <= n; h++){
            new_dp[h][0] = max(dp[0][2], dp[0][0] + pref[i-1][h]);
            new_dp[h][1] = max(dp[0][2], dp[0][0] + pref[i-1][h]);
        }
        //2) poprzednia cos miala miau
        ll mx = -oo;
        for (int h = 1; h <= n; h++){
            mx = max(mx, dp[h][0] - pref[i-1][h]);
            ckmax(new_dp[h][0], mx+pref[i-1][h]);
            ckmax(new_dp[h][1], mx+pref[i-1][h]);
        } 
        mx = -oo;
        for (int h = n; h >= 1; h--){
            mx = max(mx, dp[h][1] + pref[i][h]);
            ckmax(new_dp[h][1], mx - pref[i][h]);
        }
        debug(i);
        for (int h = 0; h <= n; h++){
            debug(h, new_dp[h]);
        }
        swap(dp, new_dp);
    }
    debug(dp);
    ll ans = 0;
    for (int h = 0; h <= n; h++){
        for (int rep = 0; rep < 3; rep++){
            ans = max(ans, dp[h][rep]);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Runtime error	762 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	5 ms	1116 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	4 ms	1116 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	6 ms	1116 KB	Output is correct
15	Correct	4 ms	1116 KB	Output is correct
16	Correct	1 ms	576 KB	Output is correct
17	Correct	14 ms	2908 KB	Output is correct
18	Correct	13 ms	2908 KB	Output is correct
19	Correct	19 ms	2752 KB	Output is correct
20	Correct	14 ms	2908 KB	Output is correct
21	Correct	13 ms	2908 KB	Output is correct
22	Correct	23 ms	4688 KB	Output is correct
23	Correct	6 ms	1472 KB	Output is correct
24	Correct	10 ms	2304 KB	Output is correct
25	Correct	5 ms	1116 KB	Output is correct
26	Correct	6 ms	1372 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	5 ms	1116 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	4 ms	1116 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	6 ms	1116 KB	Output is correct
15	Correct	4 ms	1116 KB	Output is correct
16	Correct	1 ms	576 KB	Output is correct
17	Correct	14 ms	2908 KB	Output is correct
18	Correct	13 ms	2908 KB	Output is correct
19	Correct	19 ms	2752 KB	Output is correct
20	Correct	14 ms	2908 KB	Output is correct
21	Correct	13 ms	2908 KB	Output is correct
22	Correct	23 ms	4688 KB	Output is correct
23	Correct	6 ms	1472 KB	Output is correct
24	Correct	10 ms	2304 KB	Output is correct
25	Correct	5 ms	1116 KB	Output is correct
26	Correct	6 ms	1372 KB	Output is correct
27	Correct	383 ms	71432 KB	Output is correct
28	Correct	66 ms	13648 KB	Output is correct
29	Correct	441 ms	84136 KB	Output is correct
30	Correct	448 ms	84012 KB	Output is correct
31	Correct	463 ms	84228 KB	Output is correct
32	Correct	74 ms	14816 KB	Output is correct
33	Correct	460 ms	84004 KB	Output is correct
34	Correct	446 ms	83804 KB	Output is correct
35	Correct	442 ms	76084 KB	Output is correct
36	Correct	444 ms	83812 KB	Output is correct

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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

답안 #950822

Compilation message