Cod sursa(job #2758657)

Utilizator BossBobsterRobert Alexandru Costin BossBobster Data 11 iunie 2021 21:33:58
Problema Oo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.4 kb
/*
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define f first
#define s second

ll n, ans = 0, cnt;
bool good, good2;
ll mod = 1000000007;
pll nums[50];
ll fac[50];
vector<int> cur;
vector<pii> con;
bool used[50];
ll crossProd(pll p1, pll p2)
{
    return p1.f * p2.s - p1.s * p2.f;
}
int ccw(pll p1, pll p2, pll p3)
{
    ll tmp = crossProd({p2.f - p1.f, p2.s - p1.s}, {p3.f - p1.f, p3.s - p1.s});
    if(tmp > 0) return 1;
    return -1;
}
int seg(pll p1, pll p2, pll p3, pll p4)
{
    if(ccw(p1, p2, p3) != ccw(p1, p2, p4) && ccw(p3, p4, p1) != ccw(p3, p4, p2)) return 1;
    return 0;
}
void perm(int idx)
{
    if(idx == n)
    {
        good = true;
        con.clear();
        con.push_back({cur[0], cur[1]}); con.push_back({cur[1], cur[2]}); con.push_back({cur[2], cur[0]});
        for(int i = 3; i < n; i ++)
        {
            cnt = 0;
            for(int j = 0; j < i; j ++)
            {
                good2 = true;
                for(int k = 0; k < con.size(); k ++)
                {
                    if(con[k].f == cur[j] || con[k].f == cur[i] || con[k].s == cur[j] || con[k].s == cur[i]) continue;
                    if(seg(nums[cur[i]], nums[cur[j]], nums[con[k].f], nums[con[k].s]))
                    {
                        good2 = false;
                        break;
                    }
                }
                if(good2) { con.push_back({cur[i], cur[j]}); cnt ++; }
            }
            if(cnt != 3) { good = false; break; }
        }
        if(good) ans ++;
        return;
    }
    for(int i = 0; i < n; i ++)
    {
        if(used[i]) continue;
        cur.push_back(i);
        used[i] = true;
        perm(idx + 1);
        cur.pop_back();
        used[i] = false;
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> nums[i].f >> nums[i].s;
    fac[0] = 1;
    for(int i = 1; i < n; i ++)
        fac[i] = (fac[i-1] * i) % mod;
    if(n < 9)
    {
        perm(0);
        cout << ans << "\n";
    }
    else
    {
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                for(int k = 0; k < n; k ++)
                {
                    if(i == j || i == k || j == k) continue;
                    cnt = 0;
                    for(int l = 0; l < n; l ++)
                    {
                        if(l == i || l == j || l == k) continue;
                        if(seg(nums[l], nums[i], nums[j], nums[k]) || seg(nums[l], nums[j], nums[i], nums[k]) || seg(nums[l], nums[k], nums[j], nums[i]))
                            cnt ++;
                    }
                    ans = (ans + fac[n-3-cnt] * fac[cnt]) % mod;
                }
        cout << ans << "\n";
    }
}
*/



























#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize ("O2")
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);

ifstream fin("oo.in");
ofstream fout("oo.out");

int nums[100010];
int dp[100010];
int main()
{
    int n, ans = 0;
    fin >> n;
    for(int i = 0; i < n; i ++)
        fin >> nums[i];
    dp[0] = 0; dp[1] = nums[0] + nums[1];
    for(int i = 2; i < n-1; i ++)
        dp[i] = max({dp[max(0, i-3)], dp[max(0, i-4)], dp[max(0, i-5)]}) + nums[i-1] + nums[i];
    ans = max({dp[n-3], dp[n-4], dp[n-5]});
    dp[0] = 0; dp[1] = nums[1] + nums[2];
    for(int i = 2; i < n-1; i ++)
        dp[i] = max({dp[max(0, i-3)], dp[max(0, i-4)], dp[max(0, i-5)]}) + nums[i] + nums[i+1];
    fout << max({ans, dp[n-2], dp[n-3], dp[n-4]}) << "\n";
}