Submission #924180

#	Time	Username	Problem	Language	Result	Execution time	Memory
924180		asdfGuest	Skyline (IZhO11_skyline)	C++14	0 / 100	2 ms	4696 KiB

skyline

#include <iostream>
#include <algorithm>
#include<assert.h>

using namespace std;

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

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);
    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 (stderr)

skyline.cpp: In function 'int main()':
skyline.cpp:66:25: warning: unused variable 'i1' [-Wunused-variable]
   66 |         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