square869120Contest #4

Submission #1294674

Source codeソースコード

/***********************************************
#
#      Filename: b.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-19 22:59:13
***********************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 20;
int x[maxn];
bool vis[maxn];
ll ans;
int n, k;

void incr() {
    int pre = x[0];
    ll cnt = 0;
    for (int i = 1; i < n; ++ i) {
        if (vis[i]) {
            if (x[i] <= pre) {
                cnt += pre+1 - x[i];
                pre ++;
            } else {
                pre = x[i];
            }
        } else {
            if (x[i] > pre)
                pre = x[i];
        }
    }
    if (cnt < ans)
        ans = cnt;
}

void dfs(int cur, int count) {
    if (count == k) {
        incr();
        return ;
    }
    if (cur == n) return ;
    if (count + n-cur < k) return ;
    vis[cur] = true;
    dfs(cur+1, count+1);
    vis[cur] = false;
    dfs(cur+1, count);
}


int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++ i) {
        cin >> x[i];
    }
    ans = 1L << 60;
    vis[0] = true; dfs(1, 1);
    cout << ans << endl;
    return 0;
}

Submission

Task問題 B - Buildings are Colorful!
User nameユーザ名 comsyl
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 350
Source lengthソースコード長 1256 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sub0_in1.txt,sub0_in2.txt
Subtask1 120 / 120 sub1_in1.txt,sub1_in2.txt
Subtask2 90 / 90 sub2_in1.txt,sub2_in2.txt,sub2_in3.txt
Subtask3 140 / 140 sub0_in1.txt,sub0_in2.txt,sub1_in1.txt,sub1_in2.txt,sub2_in1.txt,sub2_in2.txt,sub2_in3.txt,sub3_in1.txt,sub3_in2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sub0_in1.txt AC 1 ms 256 KB
sub0_in2.txt AC 1 ms 256 KB
sub1_in1.txt AC 1 ms 256 KB
sub1_in2.txt AC 1 ms 256 KB
sub2_in1.txt AC 1 ms 256 KB
sub2_in2.txt AC 1 ms 256 KB
sub2_in3.txt AC 1 ms 256 KB
sub3_in1.txt AC 1 ms 256 KB
sub3_in2.txt AC 1 ms 256 KB