oj.uz

답안 #680274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680274 2023-01-10T12:06:04 Z whqkrtk04 메기 농장 (IOI22_fish) C++17
44 / 100
 831 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }

typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;

ll pre(int x, int s, int e, vvll &B) {
    if(x < 0 || x >= B.size()) return 0LL;
    return B[x][e] - B[x][s];
}

vll maxpre(int i, vvvll &D) {
    vll T(D[i-1].size(), 0LL);
    for(int j = 0; j < D[i-1].size(); j++)
        for(int k = 0; k <= j; k++)
            T[j] = max(T[j], D[i-1][j][k]);
    return T;
}

vll maxall(int i, vvvll &D) {
    vll T(D[i-1].size(), 0LL);
    for(int j = 0; j < D[i-1].size(); j++)
        for(int k = 0; k < D[i-1][j].size(); k++)
            T[j] = max(T[j], D[i-1][j][k]);
    return T;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    int MX = min(N, 2+*max_element(X.begin(), X.end()));
    int MY = 2+*max_element(Y.begin(), Y.end());
    vvll A(MX, vll(MY, 0LL));
    for(int i = 0; i < M; i++) A[X[i]][Y[i]] += W[i];
    vvll B(MX, vll(MY, 0LL));
    for(int i = 0; i < MX; i++)
        for(int j = 1; j < MY; j++)
            B[i][j] = B[i][j-1]+A[i][j-1];

    vvvll D(MX, vvll(MY, vll(MY, 0LL)));
    for(int j = 0; j < MY; j++) {
        for(int k = 0; k < MY; k++) {
            if(j > k) D[1][j][k] = pre(2, 0, j, B)+pre(0, k, j, B);
            else D[1][j][k] = pre(2, 0, j, B)+pre(1, j, k, B);
        }
    }
    for(int i = 2; i < MX; i++) {
        vll MP = maxpre(i, D), MA = maxall(i, D);
        for(int j = 0; j < MY; j++) {
            for(int k = 0; k < MY; k++)
                D[i][j][0] = max(D[i][j][0], D[i-1][0][k]+pre(i-1, min(j, k), j, B)+pre(i+1, 0, j, B));
            for(int k = 1; k < MY; k++) {
                if(j > k) D[i][j][k] = MP[k]-pre(i, 0, k, B)+pre(i+1, 0, j, B)+pre(i-1, k, j, B);
                else D[i][j][k] = MA[k]-pre(i, 0, j, B)+pre(i+1, 0, j, B);
            }
        }
    }
    //cout << " " << D;
    
    ll ans = 0LL;
    for(int i = 0; i < MY; i++)
        for(int j = 0; j < MY; j++)
            ans = max(ans, D.back()[i][j]);
    return ans;
}

Compilation message

fish.cpp: In function 'll pre(int, int, int, vvll&)':
fish.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if(x < 0 || x >= B.size()) return 0LL;
      |                 ~~^~~~~~~~~~~
fish.cpp: In function 'vll maxpre(int, vvvll&)':
fish.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int j = 0; j < D[i-1].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
fish.cpp: In function 'vll maxall(int, vvvll&)':
fish.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int j = 0; j < D[i-1].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~
fish.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int k = 0; k < D[i-1][j].size(); k++)
      |                        ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 26120 KB Output is correct
3 Correct 53 ms 24768 KB Output is correct
4 Correct 49 ms 25004 KB Output is correct
5 Correct 85 ms 30132 KB Output is correct
6 Correct 66 ms 29360 KB Output is correct
7 Correct 73 ms 30048 KB Output is correct
8 Correct 86 ms 30052 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 224 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 224 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 286 ms 217260 KB Output is correct
16 Correct 6 ms 4052 KB Output is correct
17 Correct 253 ms 219892 KB Output is correct
18 Correct 251 ms 219832 KB Output is correct
19 Correct 255 ms 219856 KB Output is correct
20 Correct 252 ms 219808 KB Output is correct
21 Correct 81 ms 57944 KB Output is correct
22 Correct 304 ms 221688 KB Output is correct
23 Correct 243 ms 218384 KB Output is correct
24 Correct 262 ms 219240 KB Output is correct
25 Correct 3 ms 1620 KB Output is correct
26 Correct 263 ms 218372 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 224 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 286 ms 217260 KB Output is correct
16 Correct 6 ms 4052 KB Output is correct
17 Correct 253 ms 219892 KB Output is correct
18 Correct 251 ms 219832 KB Output is correct
19 Correct 255 ms 219856 KB Output is correct
20 Correct 252 ms 219808 KB Output is correct
21 Correct 81 ms 57944 KB Output is correct
22 Correct 304 ms 221688 KB Output is correct
23 Correct 243 ms 218384 KB Output is correct
24 Correct 262 ms 219240 KB Output is correct
25 Correct 3 ms 1620 KB Output is correct
26 Correct 263 ms 218372 KB Output is correct
27 Runtime error 831 ms 2097152 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 26120 KB Output is correct
3 Correct 53 ms 24768 KB Output is correct
4 Correct 49 ms 25004 KB Output is correct
5 Correct 85 ms 30132 KB Output is correct
6 Correct 66 ms 29360 KB Output is correct
7 Correct 73 ms 30048 KB Output is correct
8 Correct 86 ms 30052 KB Output is correct
9 Runtime error 780 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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