oj.uz

Submission #1072471

# Submission time Handle Problem Language Result Execution time Memory
1072471 2024-08-23T19:39:12 Z vjudge1 Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#include <bits/stdc++.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 = 307;
ll dp[N][N][N], pfmx[N][N][N], sfmx[N][N][N], mx[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){
        // j = i-1
        fo(c, n+1){
            fo(d, n+1){
                if(c <= d){
                    dp[i][c][d] = max(dp[i][c][d], sfmx[i-1][d][0] + gets(i, c+1, d));
                    continue;
                }
                // e >= c no cambio nada
                dp[i][c][d] = max(dp[i][c][d], sfmx[i-1][d][c]);
                // e < c quito la suma anterior agrego c
                dp[i][c][d] = max(dp[i][c][d], pfmx[i-1][d][c-1] + gets(i-1, d+1, c));
            }
        }
        // j = i-2
        if(i-2 >= 1){
            fo(c, n+1) {
                fo(d, n+1) {
                    dp[i][c][0] = max(dp[i][c][0], sfmx[i-2][d][0] + gets(i-1, 1, max(c, d)));
                }
            }
        }
        forex(j, i-3, 1){
            fo(c, n+1){
                dp[i][c][0] = max(dp[i][c][0], mx[j] + gets(i-1, 1, c));
            }
        }

        fo(d, n+1){
            pfmx[i][d][0] = dp[i][d][0];
            fore(e, 1, n+1){
                pfmx[i][d][e] = max(pfmx[i][d][e-1], dp[i][d][e] - gets(i,d+1,e));
            }
            ffo(e, n+1){
                sfmx[i][d][e] = max(sfmx[i][d][e+1], dp[i][d][e]);
            }
            mx[i] = max(mx[i],sfmx[i][d][0]);
        }
        ans = max(ans, mx[i]);
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 887 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 2396 KB Output is correct
2 Runtime error 837 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 2392 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 90 ms 170704 KB Output is correct
10 Correct 397 ms 654604 KB Output is correct
11 Correct 80 ms 170532 KB Output is correct
12 Correct 386 ms 654436 KB Output is correct
13 Correct 21 ms 50776 KB Output is correct
14 Correct 396 ms 654420 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 90 ms 170704 KB Output is correct
10 Correct 397 ms 654604 KB Output is correct
11 Correct 80 ms 170532 KB Output is correct
12 Correct 386 ms 654436 KB Output is correct
13 Correct 21 ms 50776 KB Output is correct
14 Correct 396 ms 654420 KB Output is correct
15 Correct 410 ms 654420 KB Output is correct
16 Correct 25 ms 52316 KB Output is correct
17 Correct 401 ms 656208 KB Output is correct
18 Correct 400 ms 656112 KB Output is correct
19 Correct 390 ms 656160 KB Output is correct
20 Correct 398 ms 656192 KB Output is correct
21 Correct 386 ms 656088 KB Output is correct
22 Correct 402 ms 657904 KB Output is correct
23 Correct 425 ms 654676 KB Output is correct
24 Correct 431 ms 655696 KB Output is correct
25 Correct 407 ms 654412 KB Output is correct
26 Correct 398 ms 654744 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 90 ms 170704 KB Output is correct
10 Correct 397 ms 654604 KB Output is correct
11 Correct 80 ms 170532 KB Output is correct
12 Correct 386 ms 654436 KB Output is correct
13 Correct 21 ms 50776 KB Output is correct
14 Correct 396 ms 654420 KB Output is correct
15 Correct 410 ms 654420 KB Output is correct
16 Correct 25 ms 52316 KB Output is correct
17 Correct 401 ms 656208 KB Output is correct
18 Correct 400 ms 656112 KB Output is correct
19 Correct 390 ms 656160 KB Output is correct
20 Correct 398 ms 656192 KB Output is correct
21 Correct 386 ms 656088 KB Output is correct
22 Correct 402 ms 657904 KB Output is correct
23 Correct 425 ms 654676 KB Output is correct
24 Correct 431 ms 655696 KB Output is correct
25 Correct 407 ms 654412 KB Output is correct
26 Correct 398 ms 654744 KB Output is correct
27 Execution timed out 1069 ms 193704 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 887 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -