oj.uz

답안 #626831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626831 2022-08-11T21:25:32 Z welleyth 메기 농장 (IOI22_fish) C++17
0 / 100
 1000 ms 59280 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)2e18 + 10;

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")

int cnt[NN];
vector<pair<int,long long>> val[NN];
vector<int> possibleLen[NN];

long long getSum(int x,int r){
    if(val[x].empty())
        return 0;
    if(val[x][0].first >= r)
        return 0;
    int mx = 0;
    for(auto&[col,sum] : val[x]){
        if(col < r)
            mx = sum;
    }
    return mx;
    return (upper_bound(val[x].begin(),val[x].end(),make_pair(r-1,INF))-1)->second;
}

mt19937 rnd(time(nullptr));

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    long long dp[2][333][333];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 333; j++){
            for(int t = 0; t < 333; t++){
                dp[i][j][t] = 0;
            }
        }
    }
    set<int> st[N+22];
    for(int i = 0; i < M; i++){
//        g[X[i]+2][Y[i]] = W[i];
        val[X[i]+2].push_back(make_pair(Y[i],W[i]));
        for(int j = max(2,X[i]+1); j <= X[i]+3; j++){
            st[j].insert(Y[i]+1);
        }
    }

    for(int i = 0; i < N+2; i++){
        st[i].insert(0);
        possibleLen[i] = vector<int>(st[i].begin(),st[i].end());
        sort(val[i].begin(),val[i].end());
        for(int j = 1; j < val[i].size(); j++){
            val[i][j].second += val[i][j-1].second;
        }
    }

//    cerr << getSum(2,3) << "\n";
//    return 0;

    long long ans = 0;

    for(int i = 2; i < N+2; i++){
        int pr[2];
        for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                int lcur = possibleLen[i][cur];
                int l1 = possibleLen[i-2][pr[1]];
                pr[0] = upper_bound(possibleLen[i-1].begin(),possibleLen[i-1].end(),min(l1,lcur)) - possibleLen[i-1].begin() - 1;
                for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
                    int l0 = possibleLen[i-1][pr[0]];
                    if(lcur <= l0){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,lcur));
                    } else if(lcur <= l1){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0));
                    } else {
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0)
                                            + max(0ll,getSum(i-1,lcur)-getSum(i-1,l0)) - max(0ll,getSum(i-1,l1)-getSum(i-1,l0)));
                    }
                    ans = max(ans,dp[1][pr[0]][cur]);
//                    cerr << i << " " << l1 << " " << l0 << " " << lcur << " " << dp[1][pr[0]][cur] << "\n";
//                    if(dp[0][pr[0]][cur] == 0)
//                        continue;
                }
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
                dp[0][pr[1]][pr[0]] = 0;
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[0][pr[0]][cur] = dp[1][pr[0]][cur];
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[1][pr[0]][cur] = 0;
            }
        }
    }
//    for(int i = 0; i < N+2; i++){
//        for(int j = 0; j < 10; j++){
//            for(int t = 0; t < 10; t++){
//                ans = max(ans,dp[i][j][t]);
//            }
//        }
//    }

    return ans;
}
/**
10000 2
0 0 1
0 1 1

5 4
0 2 5
1 1 2
4 4 1
3 3 3


**/

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j = 1; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:67:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:89:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:93:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:94:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:98:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:99:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Execution timed out 1097 ms 37608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19156 KB Output is correct
2 Correct 24 ms 19260 KB Output is correct
3 Incorrect 55 ms 23648 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6628 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Incorrect 4 ms 6740 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '163929066907'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6628 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Incorrect 4 ms 6740 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '163929066907'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 3 ms 6628 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Incorrect 4 ms 6740 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '163929066907'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19156 KB Output is correct
2 Correct 24 ms 19260 KB Output is correct
3 Incorrect 55 ms 23648 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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