oj.uz

답안 #835739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835739 2023-08-23T18:59:42 Z ALeonidou 메기 농장 (IOI22_fish) C++17
0 / 100
 20 ms 5644 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

typedef vector <ll> vi;
typedef vector <long long > vl;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;


void printVct(vl &v, string s = ""){
    cout<<s<<": ";
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

#define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl;
#define N 300
#define MAXY 9 // Y[i] + 1

ll n,m;
long long arr[N+1][MAXY+1];
long long dp[N+1][MAXY+1][MAXY+1];
long long s[N+1][MAXY+1];

long long calc(ll u, ll l, ll r){       // 0 <= x <= 9
    
    if (u < 0){
        cout<<"ERROR!! "<<u<<" "<<l<<" "<<r<<endl<<endl;
        exit(1);
    }

    if (l > r){
        return 0;
    }
    l--, r--;
    if (l == 0){
        return s[u][r];
    }
    else{
        return s[u][r] - s[u][l-1];
    }
}

void printDP(ll v = MAXY){
    for (ll k=0; k<=v; k++){
        cout<<"k: "<<k<<endl;
        for (ll i = 0; i<n; i++){
            cout<<i<<": ";
            for (ll j =0; j<=MAXY; j++){
                cout<<dp[i][j][k];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
}

long long solve(){
    //prep line 0
    for (ll j =0; j<=MAXY; j++){
        for (ll k =0; k<=MAXY; k++){
            dp[0][j][k] = 0;
        }
    }

    //prep line 1
    for (ll j =0; j<=MAXY; j++){
        for (ll k =0; k<=MAXY; k++){
            if (j == k) dp[1][j][k] = 0;
            else if (j > k){
                dp[1][j][k] = calc(0, k+1, j);
            }
            else{
                dp[1][j][k] = calc(1, j+1, k);
            }
        }
    }

    // printDP();

    for (ll i =2; i<n; i++){
        for (ll j = 0; j<=MAXY; j++){
            for (ll k =0; k<=MAXY; k++){
                long long ans = 0, c;
                for (ll y =0; y<=j; y++){
                    // dbg(y);
                    c = dp[i-1][k][y] + calc(i-1, max(y,k+1), j);      //chek indexes
                    ans=max(ans, c);
                }

                for (ll y =j+1; y<=MAXY; y++){
                    c = dp[i-1][k][y];
                    ans = max(ans, c);
                }

                dp[i][j][k] = ans;
            }
        }
    }

    long long ans =0;
    for (ll i =0; i<=MAXY; i++){
        for (ll j =0; j<=MAXY; j++){
            ans = max(ans, dp[n-1][i][j]);
        }
    }

    return ans;
}

long long max_weights(int NN, int M, vi X, vi Y, vi W) {
    n= NN, m =M;

    for (ll i =0 ; i<m; i++){
        arr[X[i]][Y[i]] = W[i];
    }

    for (ll i =0; i<n; i++){
        s[i][0] = arr[i][0];
        for (ll j = 1; j< MAXY; j++){
            s[i][j] =s[i][j-1] + arr[i][j-1];
        }
    }

    // printArr2D(s,n,MAXY,"s");

    long long ans = solve();

    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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