oj.uz

Submission #514808

# Submission time Handle Problem Language Result Execution time Memory
514808 2022-01-18T13:48:23 Z 79brue None (KOI17_cook) C++14
0 / 100
 2 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, s, e; ll t; /// m: 학원 수, n: 강좌 수
ll arr[3002][3002];
ll sum[3002][3002];
int prv[3002];
list<pair<int, ll> > lst[3002];
vector<pair<ll, int> > vec;

ll DP[3002][3002];
ll ans = LLONG_MAX;

int main(){
    scanf("%d %d %d %d %lld", &m, &n, &s, &e, &t);
    for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) scanf("%lld", &arr[j][i]), sum[j][i] = sum[j-1][i] + arr[j][i];
    for(int i=1; i<=m; i++) scanf("%d", &prv[i]);

    for(int i=1; i<=m; i++) lst[i].push_back(make_pair(-1, 1e18));

    for(int i=1; i<=n; i++){
        /// DP 값을 덱에 반영한다.
        if(i >= s){
            vec.clear();
            for(int j=1; j<=m; j++) vec.push_back(make_pair(DP[i-s][j], j));
            sort(vec.begin(), vec.end());

            for(int j=1; j<=m; j++){
                int pnt = 0;
                while(vec[pnt].second == j || vec[pnt].second == prv[j]) pnt++;
                ll w = vec[pnt].first - sum[i-s][j];
                int x = vec[pnt].second;

                while(!lst[j].empty() && lst[j].back().second >= w) lst[j].pop_back();
                lst[j].push_back(make_pair(i-s, w));
            }
        }

        /// DP 값을 계산한다.
        for(int j=1; j<=m; j++){
            while(lst[j].front().first < i-e) lst[j].pop_front();
            assert(!lst[j].empty());
            DP[i][j] = lst[j].front().second + sum[i][j] + t;
            if(i==n) ans = min(ans, DP[i][j] - t);
        }
    }

    for(int j=1; j<=m; j++){
        ans = min(ans, lst[j].front().second + sum[n][j]);
    }

    printf("%lld", ans);
}

Compilation message

cook.cpp: In function 'int main()':
cook.cpp:35:21: warning: unused variable 'x' [-Wunused-variable]
   35 |                 int x = vec[pnt].second;
      |                     ^
cook.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d %d %d %d %lld", &m, &n, &s, &e, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:19:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) scanf("%lld", &arr[j][i]), sum[j][i] = sum[j-1][i] + arr[j][i];
      |                                                     ~~~~~^~~~~~~~~~~~~~~~~~~~
cook.cpp:20:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     for(int i=1; i<=m; i++) scanf("%d", &prv[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Halted 0 ms 0 KB -