oj.uz

Submission #955354

# Submission time Handle Problem Language Result Execution time Memory
955354 2024-03-30T08:16:18 Z Gray Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
// #include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#define M_PI 3.14159265358979323846
#define ll long long
using ld = double;
#define ff first
#define ss second
#define ln "\n"
#define gcd(x,y) __gcd(x,y)
using namespace std;

// const ll MOD = 1e9+7;
const ll INF = 2e18;
// const ll MAXN = 1e6+1;

ll max_weights(int n, int m, vector<int> cx, vector<int> cy, vector<int> cw){
    n++;
    vector<pair<pair<ll, ll>, ll>> fish(m);
    for (ll i=0; i<m; i++){
        fish[i] = {{cx[i], cy[i]+1}, cw[i]};
    }
    sort(fish.begin(), fish.end(), [](auto op1, auto op2)->bool{
        return op1.ff.ss<op2.ff.ss;
    });
    vector<vector<ll>> A(n, vector<ll>(n));
    for (ll i=0; i<m; i++){
        A[fish[i].ff.ff][fish[i].ff.ss]=fish[i].ss;
    }
    vector<vector<ll>> pref(n, vector<ll>(n,0));
    for (ll i=0; i<n; i++){
        for (ll j=0; j<n; j++){
            pref[i][j] = (j==0?A[i][j]:pref[i][j-1]+A[i][j]);
        }
    }
    // return 0;
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(n, 0)));
    vector<vector<vector<ll>>> dp2(n, vector<vector<ll>>(n, vector<ll>(n, 0)));
    for (ll i=1; i<n; i++){
        for (ll j=0; j<n; j++){
            for (ll k=0; k<n; k++){
                if (j>k){
                    dp[i][j][k] = max(dp[i-1][k][n-1], dp[i-1][k][k]+pref[i-1][j]-pref[i-1][k]);
                }else dp[i][j][k] = dp[i-1][k][n-1]+pref[i][k]-pref[i][j];
                if (k) dp[i][j][k]=max(dp[i][j][k], dp[i][j][k-1]);
            }
            // for (ll k=n-1; k>=0; k--){
            //     dp2[i][j][k] = dp[i][j][k]+(i+1<n?A[i+1][j]:0);
            //     if (k+1<n) dp2[i][j][k]=max(dp2[i][j][k+1], dp2[i][j][k]);
            // }
        }
    }
    ll mx = 0;
    // for (ll i=0; i<n; i++){
    //     cout << i << ": \n";
    //     for (ll j=0; j<n; j++){
    //         for (ll k=0; k<n; k++){
    //             cout << dp[i][j][k] << " ";
    //         }
    //         cout << ln;
    //     }
    // }
    for (ll i=0; i<n; i++){
        mx = max(mx, dp[n-2][i][n-1]);
    }
    return mx;
}

// int main(){
//  ios_base::sync_with_stdio(false);
//  cin.tie(NULL);
//  ll t=1;
//  cin >> t;
//  // while (t--) solve();
// }


// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));

//   std::vector<int> X(M), Y(M), W(M);
//   for (long long i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//   }

//   long long result = max_weights(N, M, X, Y, W);
//   printf("%lld\n", result);
//   return 0;
// }

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 1853636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 916 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 Execution timed out 1125 ms 1761316 KB Time limit exceeded
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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 37 ms 56528 KB Output is correct
10 Correct 252 ms 435156 KB Output is correct
11 Correct 39 ms 56416 KB Output is correct
12 Correct 257 ms 435040 KB Output is correct
13 Correct 5 ms 7784 KB Output is correct
14 Correct 255 ms 435040 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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 37 ms 56528 KB Output is correct
10 Correct 252 ms 435156 KB Output is correct
11 Correct 39 ms 56416 KB Output is correct
12 Correct 257 ms 435040 KB Output is correct
13 Correct 5 ms 7784 KB Output is correct
14 Correct 255 ms 435040 KB Output is correct
15 Correct 261 ms 435240 KB Output is correct
16 Correct 7 ms 8040 KB Output is correct
17 Correct 266 ms 438024 KB Output is correct
18 Correct 269 ms 438100 KB Output is correct
19 Correct 286 ms 438092 KB Output is correct
20 Correct 272 ms 438100 KB Output is correct
21 Correct 265 ms 438084 KB Output is correct
22 Correct 288 ms 441116 KB Output is correct
23 Correct 257 ms 435532 KB Output is correct
24 Correct 263 ms 437076 KB Output is correct
25 Correct 252 ms 435280 KB Output is correct
26 Correct 274 ms 435536 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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 37 ms 56528 KB Output is correct
10 Correct 252 ms 435156 KB Output is correct
11 Correct 39 ms 56416 KB Output is correct
12 Correct 257 ms 435040 KB Output is correct
13 Correct 5 ms 7784 KB Output is correct
14 Correct 255 ms 435040 KB Output is correct
15 Correct 261 ms 435240 KB Output is correct
16 Correct 7 ms 8040 KB Output is correct
17 Correct 266 ms 438024 KB Output is correct
18 Correct 269 ms 438100 KB Output is correct
19 Correct 286 ms 438092 KB Output is correct
20 Correct 272 ms 438100 KB Output is correct
21 Correct 265 ms 438084 KB Output is correct
22 Correct 288 ms 441116 KB Output is correct
23 Correct 257 ms 435532 KB Output is correct
24 Correct 263 ms 437076 KB Output is correct
25 Correct 252 ms 435280 KB Output is correct
26 Correct 274 ms 435536 KB Output is correct
27 Execution timed out 1064 ms 2097152 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1125 ms 1761316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 1853636 KB Time limit exceeded
2 Halted 0 ms 0 KB -