oj.uz

Submission #1077102

# Submission time Handle Problem Language Result Execution time Memory
1077102 2024-08-27T00:34:12 Z vjudge1 Catfish Farm (IOI22_fish) C++17
35 / 100
 870 ms 2097152 KB 
#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][2], pfmx[N][2], sfmx[N][2], sfmx2[N];
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) {
        pfmx[0][0] = dp[i-1][0][0];
        fore(c, 1, n+1) pfmx[c][0] = max(pfmx[c-1][0], dp[i-1][c][0] - gets(i-1, 1, c));
 
        sfmx[n][0] = dp[i-1][n][0];
        ffo(c, n) sfmx[c][0] = max(sfmx[c+1][0], dp[i-1][c][0]);
 
        sfmx2[n] = dp[i-1][n][0] + gets(i, 1, n);
        ffo(c, n) sfmx2[c] = max(sfmx2[c+1], dp[i-1][c][0] + gets(i, 1, c));
 
        pfmx[0][1] = dp[i-1][0][1];
        fore(c, 1, n+1) pfmx[c][1] = max(pfmx[c-1][1], dp[i-1][c][1]);
 
        sfmx[n][1] = dp[i-1][n][1] + gets(i, 1, n);
        ffo(c, n) sfmx[c][1] = max(sfmx[c+1][1], dp[i-1][c][1] + gets(i, 1, c));
        fo(c, n+1) {
            dp[i][c][0] = max({gets(i-1, 1, c) + pfmx[c][0], sfmx[c+1][0], pfmx[n][1]});
            dp[i][c][1] = max({gets(i-1, 1, c) + pfmx[c][0], -gets(i, 1, c) + sfmx2[c+1], sfmx[c][1] - gets(i, 1, c), (c>0?pfmx[c-1][1]:0)});
            ans = max(ans, dp[i][c][1]);
        }
    }
    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 807 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 600 KB Output is correct
2 Runtime error 870 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 830 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 1 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 3 ms 4532 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 3 ms 4532 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 10 ms 6228 KB Output is correct
18 Correct 11 ms 6232 KB Output is correct
19 Correct 11 ms 6236 KB Output is correct
20 Correct 11 ms 6252 KB Output is correct
21 Correct 11 ms 6208 KB Output is correct
22 Correct 18 ms 8028 KB Output is correct
23 Correct 4 ms 4748 KB Output is correct
24 Correct 9 ms 5720 KB Output is correct
25 Correct 3 ms 4444 KB Output is correct
26 Correct 4 ms 4668 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 3 ms 4532 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 10 ms 6228 KB Output is correct
18 Correct 11 ms 6232 KB Output is correct
19 Correct 11 ms 6236 KB Output is correct
20 Correct 11 ms 6252 KB Output is correct
21 Correct 11 ms 6208 KB Output is correct
22 Correct 18 ms 8028 KB Output is correct
23 Correct 4 ms 4748 KB Output is correct
24 Correct 9 ms 5720 KB Output is correct
25 Correct 3 ms 4444 KB Output is correct
26 Correct 4 ms 4668 KB Output is correct
27 Runtime error 408 ms 573192 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 830 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 807 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -