Submission #514812

#	Time	Username	Problem	Language	Result	Execution time	Memory
514812		79brue	요리 강좌 (KOI17_cook)	C++14	100 / 100	831 ms	123928 KiB

cook

#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();
            DP[i][j] = lst[j].front().second + sum[i][j] + t;
            if(i==n) ans = min(ans, DP[i][j] - t);
        }
    }

    for(int i=n-s; i<=n-1; i++){
        vec.clear();
        for(int j=1; j<=m; j++) vec.push_back(make_pair(DP[i][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;
            int x = vec[pnt].second;

            ans = min(ans, w + sum[n][j] - sum[i][j]);
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:35:21: warning: unused variable 'x' [-Wunused-variable]
   35 |                 int x = vec[pnt].second;
      |                     ^
cook.cpp:59:17: warning: unused variable 'x' [-Wunused-variable]
   59 |             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: 13 / 13
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 44 / 44