oj.uz

답안 #924183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924183 2024-02-08T15:59:20 Z asdfGuest 스카이라인 (IZhO11_skyline) C++14
0 / 100
 1 ms 348 KB 
#include <iostream>
#include <algorithm>
#include<assert.h>

using namespace std;

int n, a[10001], dp[4][10001], dp2[4][10001];

inline int get_type(int a1, int a2, int a3) {
    int min3 = min(a1, min(a2, a3));

    if (
        (min3 == a1 && min3 == a2 && min3 == a3) ||
        (min3 != a1 && min3 == a2 && min3 != a3) ||
        (min3 != a1 && min3 != a2 && min3 == a3) ||
        (min3 == a1 && min3 == a2 && min3 != a3) ||
        (min3 != a1 && min3 == a2 && min3 == a3) )
        return 1;
    else
        return 2;
}
inline pair<int, int> get_t1cost(int a1, int a2, int a3) {
    int cost = 0;
    
    int c3 = min(a1, min(a2, a3));
    a1 -= c3;
    a2 -= c3;
    a3 -= c3;
    cost += 7 * c3;

    int c2 = min(a1, a2);
    a1 -= c2;
    a2 -= c2;
    cost += 5 * c2;

    int c1 = a1 + a2;
    a1 = 0;
    a2 = 0;
    cost += 3 * c1;

    return {cost, a3};
}

int main(void) {
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    a[n] = 0;

    for (int i = n - 1; i >= n - 2; i--) {
        for (int j = a[i]; j >= 0; j--) {
            int i0 = i % 4;

            auto t = get_t1cost(j, a[i + 1], 0);
            dp[i0][j] = t.first;
            
            dp2[i0][j] = t.first - j * 2;
            if (j + 1 <= a[i])
                dp2[i0][j] = min(dp2[i0][j], dp2[i0][j + 1]);
        }//assert(0);
    }
    while (true) {}
    for (int i = n - 3; i >= 0; i--) {
        int i0 = i % 4, i1 = (i + 1) % 4, i2 = (i + 2) % 4, i3 = (i + 3) % 4;

        for (int j = a[i]; j >= 0; j--) {

            int a1 = j, a2 = a[i + 1], a3 = a[i + 2], a4 = a[i + 3];
            int cost;
            //printf("---- %d %d ----\n", i, j);
            if (get_type(a1, a2, a3) == 1 || a4 == 0) {
                auto t = get_t1cost(a1, a2, a3);
                cost = t.first + dp[i2][t.second];
                //printf("type 1");
                //printf("t.first %d   cost %d\n", t.first, cost);
            }

            else {
                cost = 0;
                cost += (2 * a1 + 3 * a2 + 4 * a3);
                cost += dp2[i3][max(0, max(a4 - a3, a1 - a2 + a4))];
                cost += 2 * (a4 - a3);
                //printf("type 2\n");
                //printf("dp2 %d  %d    cost %d\n", max(0, max(a4 - a3, a1 - a2 + a4)), dp2[i + 3][max(0, max(a4 - a3, a1 - a2 + a4))], cost);
            }
            
            dp[i0][j] = cost;

            dp2[i0][j] = cost - j * 2;
            if (j + 1 <= a[i])
                dp2[i0][j] = min(dp2[i0][j], dp2[i0][j + 1]);

            //printf("\n");
        }
    }
    
    printf("%d\n", dp[0 % 4][a[0]]);
    //system("pause");
    return 0;
}

Compilation message

skyline.cpp: In function 'int main()':
skyline.cpp:65:25: warning: unused variable 'i1' [-Wunused-variable]
   65 |         int i0 = i % 4, i1 = (i + 1) % 4, i2 = (i + 2) % 4, i3 = (i + 3) % 4;
      |                         ^~
skyline.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
skyline.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 100.0

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