답안 #835524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835524 2023-08-23T15:29:02 Z ALeonidou 메기 농장 (IOI22_fish) C++17
0 / 100
19 ms 4300 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 MAXN 300
#define MAXY 9 // Y[i] + 1

ll n,m;
long long arr[MAXN+1][MAXY+1];
long long dp[MAXN+1][MAXY+1][MAXY+1];
long long s[MAXN+1][MAXY+1];
void tabb(ll n) {
    for (ll i=0; i<n; i++) cout<<"\t";
}

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];
    }
}

long long solve(ll i, ll j, ll k){
    // dbg3(i,j,k);
    //base case
    if (i < 0) return 0;

    //general case
    if (dp[i][j][k] == -1){
        long long ans = 0,c;
        for (ll y =0; y<=j; y++){
            // dbg(y);
            c = solve(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 = solve(i-1,k,y);
            ans = max(ans, c);
        }

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

    return dp[i][j][k];
}

long long init_solve(){
    //reset
    for (ll i=0;i<n;i++){
        for (ll j =0;j <=MAXY; j++){
            for (ll k =0; k<=MAXY; k++){
                dp[i][j][k] = -1;
            }
        }
    }

    //prep line 0
    for (ll i =0; i<=MAXY; i++){
        for (ll j =0; j<=MAXY; j++){
            dp[0][i][j] = -1;
        }
    }

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

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

    return ans;
}

long long max_weights(int N, int M, vi X, vi Y, vi W) {
    n= N, 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");

    // dbg3(calc(0,3,5), calc(2, 1, 4), calc(4, 3, 8));

    long long ans = init_solve();

    return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 4300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 4300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -