답안 #1019675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019675	2024-07-11T07:18:02 Z	Gray	메기 농장 (IOI22_fish)	C++17	52 / 100	831 ms	2097152 KB

fish

#include "fish.h"

#include <cassert>
#include <deque>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;



long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    ll n=N, m=M;
    vector a(N, vector<ll>(N));
    for (ll i=0; i<m; i++){
        a[X[i]][Y[i]]+=W[i];
    }
    vector dp(N, vector<pair<ll, ll>>(N+1));
    for (ll i=1; i<N; i++){
        // cout << i << ": " << endl;
        deque<pair<ll, ll>> bestU;
        pair<ll, ll> mx = {-1, -1};
        ll sum=0, rsum=0;
        for (ll j=0; j<N; j++) rsum+=a[i][j];
        sum=rsum;
        for (ll j=N; j>=0; j--){
            if (j<N) sum-=a[i][j];
            if (max(dp[i-1][j].ff, dp[i-1][j].ss)+sum>mx.ff){
                mx = {max(dp[i-1][j].ff, dp[i-1][j].ss)+sum, j};
                bestU.push_back(mx);
                // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
        }
        sum=0;
        for (ll j=0; j<=N; j++){
            if (j) sum+=a[i][j-1];
            if (bestU.back().ss<j) {
                bestU.pop_back();
                // cout << "Remove: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
            dp[i][j].ss=bestU.back().ff-sum;
        }
        if (i>1){ //-Change-
            // cout << i << ": ";
            pair<ll, ll> best = {-1, -1};
            for (ll j=0; j<N+1; j++){
                best=max(best, {max(dp[i-2][j].ff, dp[i-2][j].ss), j});
            }
            ll osum=0;
            for (ll j=0; j<best.ss; j++){
                osum+=a[i-1][j];
            }
            // cout << osum << " -> ";
            sum=0;
            for (ll j=0; j<=n; j++){
                if (j) sum+=a[i-1][j-1];
                dp[i][j].ff=best.ff+max(sum, osum);
            }
        }
        assert(bestU.size()<=1);
        while (!bestU.empty()) bestU.pop_back();
        mx = {-1, -1};
        sum=rsum=0;
        for (ll j=0; j<N; j++) rsum+=a[i-1][j];
        for (ll j=0; j<=N; j++){
            if (j) sum+=a[i-1][j-1];
            if (rsum-sum+dp[i-1][j].ff>mx.ff){
                mx = {rsum-sum+dp[i-1][j].ff, j};
                bestU.push_back(mx);
            }
        }
        sum=0;
        for (ll j=N; j>=0; j--){
            if (j<N) sum+=a[i-1][j];
            if (bestU.back().ss>j) bestU.pop_back();
            dp[i][j].ff=max(dp[i][j].ff, bestU.back().ff-sum);
        }
    }
    // for (ll i=N; i>=0; i--){
    //     for (ll j=0; j<N; j++) cout << dp[j][i].ff << " ";
    //     cout << endl;
    // }
    // for (ll i=N; i>=0; i--){
    //     for (ll j=0; j<N; j++) cout << dp[j][i].ss << " ";
    //     cout << endl;
    // }
    ll res=0;
    for (ll i=0; i<=n; i++){
        res=max(res, max(dp[n-1][i].ff,dp[n-1][i].ss));
    }
    return res;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	779 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	348 KB	Output is correct
2	Runtime error	829 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	831 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	348 KB	Output is correct
2	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	2 ms	2652 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	2 ms	2396 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	2 ms	2652 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	2 ms	2396 KB	Output is correct
15	Correct	3 ms	2392 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	16 ms	4312 KB	Output is correct
18	Correct	10 ms	4188 KB	Output is correct
19	Correct	12 ms	4188 KB	Output is correct
20	Correct	10 ms	4188 KB	Output is correct
21	Correct	10 ms	4280 KB	Output is correct
22	Correct	20 ms	5988 KB	Output is correct
23	Correct	3 ms	2732 KB	Output is correct
24	Correct	8 ms	3688 KB	Output is correct
25	Correct	2 ms	2408 KB	Output is correct
26	Correct	4 ms	2692 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	2 ms	2652 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	2 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	2 ms	2396 KB	Output is correct
15	Correct	3 ms	2392 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	16 ms	4312 KB	Output is correct
18	Correct	10 ms	4188 KB	Output is correct
19	Correct	12 ms	4188 KB	Output is correct
20	Correct	10 ms	4188 KB	Output is correct
21	Correct	10 ms	4280 KB	Output is correct
22	Correct	20 ms	5988 KB	Output is correct
23	Correct	3 ms	2732 KB	Output is correct
24	Correct	8 ms	3688 KB	Output is correct
25	Correct	2 ms	2408 KB	Output is correct
26	Correct	4 ms	2692 KB	Output is correct
27	Correct	186 ms	212056 KB	Output is correct
28	Correct	49 ms	22360 KB	Output is correct
29	Correct	219 ms	224596 KB	Output is correct
30	Correct	224 ms	224600 KB	Output is correct
31	Correct	217 ms	224608 KB	Output is correct
32	Correct	59 ms	19540 KB	Output is correct
33	Correct	217 ms	224848 KB	Output is correct
34	Correct	222 ms	224604 KB	Output is correct
35	Correct	184 ms	216656 KB	Output is correct
36	Correct	230 ms	224592 KB	Output is correct

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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

답안 #1019675

Compilation message