Submission #199045

#	Time	Username	Problem	Language	Result	Execution time	Memory
199045		Ruxandra985	Aliens (IOI16_aliens)	C++14	4 / 100	6 ms	380 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
using namespace std;
pair <long long,long long> v[DIMN];
long long dp[DIMN];
long long cnt[DIMN];
int cmp (pair <long long,long long> x , pair <long long,long long> y){
    if (x.first != y.first)
        return x.first < y.first;
    return x.second > y.second;
}
pair <long long,long long> solve (long long x , long long n){ /// cost x , n intervale
    long long i , j;
    /// nu cred ca bag cu cht azi ca mi e somn
    for (i = 1 ; i <= n ; i++){
        cnt[i] = 1;
        dp[i] = (v[i].second - v[1].first + 1) * (v[i].second - v[1].first + 1) - x;
        for (j = 1 ; j <= i ; j ++){
            if (-x + dp[j - 1] + (v[i].second - v[j].first + 1) * (v[i].second - v[j].first + 1) - max (0LL , (v[j-1].second - v[j].first + 1)) * max (0LL , (v[j-1].second - v[j].first + 1)) <= dp[i]){
                    dp[i] = -x + dp[j - 1] + (v[i].second - v[j].first + 1) * (v[i].second - v[j].first + 1) - max (0LL , (v[j-1].second - v[j].first + 1)) * max (0LL , (v[j-1].second - v[j].first + 1));
                    cnt[i] = 1 + cnt[j - 1];
                }
        }
    }
    return make_pair(cnt[n] , dp[n]);

}
long long take_photos (int n , int m , int k , vector <int> r , vector <int> c){
    long long st , dr , mid;
    long long i , n2 , rm;
    pair <long long,long long> rez;
    for (i=0;i<n;i++){
        v[i+1] = make_pair(r[i] + 1 , c[i] + 1);
        if (v[i+1].first > v[i+1].second)
            swap (v[i+1].first , v[i+1].second);
    }
    sort (v + 1 , v + n + 1 , cmp);
    n2 = 0;
    rm = 0;
    for (i=1;i<=n;i++){ /// nu iau intervale incluse total unul in altul
        if (rm < v[i].second)
            v[++n2] = v[i];
        rm = max(rm , v[i].second);
    }
    n = n2;

    st = 0;
    dr = 1000000000000000000;
    while (st <= dr){
        mid = (st + dr)/2;
        rez = solve(mid , n2);
        if (rez.first > k)
            st = mid + 1;
        else dr = mid - 1;
    }
    rez = solve(dr , n2);
    return rez.second + dr * rez.first;

}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40