Codeforces Coder-Strike 2014 - Round 2, problem: (C) Jeopardy! solution

general
, , , ,
1

Codeforces Coder-Strike 2014 - Round 2, problem: © Jeopardy! : http://codeforces.com/contest/413/problem/C

Codeforces Coder-Strike 2014 - Round 2, problem: © Jeopardy! solution: http://ideone.com/BPHLAz

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int n, m, a[105], b, c[105]={0}, it;
    long long int s=0, d[105]={0};
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &a[i]), d[i]=a[i];
    for(int i=0; i<m; i++) scanf("%d", &b), c[b-1]++;
    for(int i=0; i<n; i++) if(c[i]==0) s+=a[i];
    sort(d, d+n);
    it=n-1;
    for(int i=0; i<n; i++) if(c[i]) s+=max(s, d[it]), it--;
    printf("%I64d\n", s);
    return 0;
}

note: R2 needs the highest point possible at the end of the game. so to do that, in hope of getting higher sum start with non-auction questions. and summing them all up, move onto auction questions. the advantage of auction questions is that they may get increased to R2’s collected total points. and for every auction question start with highest point possible, in order to achieve that we sorted array d[]. looping through every question check whether that is auction question or not, if yes, then add the highest available auction point to collection (s+=max(s, d[it])). to get that highest point available we already sorted d[] array and we iterate from last index to the first (it=n-1, d[it], it--).