Submission #1077093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077093	2024-08-26T22:44:28 Z	vjudge1	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	2097152 KB

fish

#include <bits/stdc++.h>
// #include "prison.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
// #pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
 
#define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)

bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;}
bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;}
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
ll gauss(ll n){return (n*(n+1))/2;}
const int N = 3000;
ll dp[N][N][3];
ll max_weights(int n,int m,vi x,vi y,vi w) {
    vector<vll> arr(n+4, vll(n+4, 0)), pf(n+4, vll(n+4, 0));
    fo(i, m) x[i]++, y[i]++;
    fo(i, m) arr[x[i]][y[i]] = w[i];
    fore(i, 1, n+1) {
        fore(j, 1, n+1) {
            pf[i][j] = (i ? pf[i][j-1] : 0) + arr[i][j];
        }
    }
    auto gets = [&](int i,int l,int r) {
        if(l > r) return 0ll;
        assert(l >= 1);
        return pf[i][r] - pf[i][l-1];
    };
    ll ans = 0;
    fore(i, 2, n+1) {
        fo(c, n+1) {
            fo(d, n+1) {
                dp[i][c][0] = max({dp[i][c][0], dp[i-1][d][0], dp[i-1][d][1] + gets(i-1, 1, c) - gets(i-1, 1, d), dp[i-1][d][2]});
                dp[i][c][1] = max({dp[i][c][1], dp[i-1][d][0], dp[i-1][d][1] + gets(i-1, 1, c) - gets(i-1, 1, d), dp[i-1][d][2]});
                ll s = gets(i, 1, d) - gets(i, 1, c);
                dp[i][c][2] = max({dp[i][c][2] - s, dp[i-1][d][0], dp[i-1][d][1] + gets(i-1, 1, c) - gets(i-1, 1, d), dp[i-1][d][2]}) + s;
            }
            assert(dp[i][c][0] == dp[i][c][1]);
            ans = max(ans, max(dp[i][c][2], dp[i][c][0]));
        }
    }
    return ans;
}
// void test_case() {
//     int n, m;
//     cin >> n >> m;
//     vi x(m), y(m), w(m);
//     fo(i, m) cin >> x[i] >> y[i] >> w[i];
//     cout << max_weights(n, m, x, y, w) << '\n';   
// }

// int main(){cin.tie(0)->sync_with_stdio(0);
//     int t=1;
//     // cin >> t;
//     while(t--)test_case();
// }

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	808 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Runtime error	819 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	804 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	20 ms	1884 KB	Output is correct
10	Correct	153 ms	5120 KB	Output is correct
11	Correct	20 ms	1884 KB	Output is correct
12	Correct	161 ms	5220 KB	Output is correct
13	Correct	3 ms	860 KB	Output is correct
14	Correct	153 ms	5048 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	20 ms	1884 KB	Output is correct
10	Correct	153 ms	5120 KB	Output is correct
11	Correct	20 ms	1884 KB	Output is correct
12	Correct	161 ms	5220 KB	Output is correct
13	Correct	3 ms	860 KB	Output is correct
14	Correct	153 ms	5048 KB	Output is correct
15	Correct	152 ms	5200 KB	Output is correct
16	Correct	3 ms	856 KB	Output is correct
17	Correct	169 ms	6864 KB	Output is correct
18	Correct	160 ms	6996 KB	Output is correct
19	Correct	161 ms	7016 KB	Output is correct
20	Correct	162 ms	6840 KB	Output is correct
21	Correct	161 ms	6996 KB	Output is correct
22	Correct	168 ms	8784 KB	Output is correct
23	Correct	151 ms	5428 KB	Output is correct
24	Correct	158 ms	6356 KB	Output is correct
25	Correct	153 ms	5092 KB	Output is correct
26	Correct	153 ms	5460 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	20 ms	1884 KB	Output is correct
10	Correct	153 ms	5120 KB	Output is correct
11	Correct	20 ms	1884 KB	Output is correct
12	Correct	161 ms	5220 KB	Output is correct
13	Correct	3 ms	860 KB	Output is correct
14	Correct	153 ms	5048 KB	Output is correct
15	Correct	152 ms	5200 KB	Output is correct
16	Correct	3 ms	856 KB	Output is correct
17	Correct	169 ms	6864 KB	Output is correct
18	Correct	160 ms	6996 KB	Output is correct
19	Correct	161 ms	7016 KB	Output is correct
20	Correct	162 ms	6840 KB	Output is correct
21	Correct	161 ms	6996 KB	Output is correct
22	Correct	168 ms	8784 KB	Output is correct
23	Correct	151 ms	5428 KB	Output is correct
24	Correct	158 ms	6356 KB	Output is correct
25	Correct	153 ms	5092 KB	Output is correct
26	Correct	153 ms	5460 KB	Output is correct
27	Execution timed out	1070 ms	143348 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	804 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	808 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #1077093

Compilation message