akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
typedef long long ll;
typedef std::pair<ll,int> P;
const int N=1e5+5;
const ll INF=1e18;
ll tot=1e15;
int n,m,s,t;
std::vector<int> g[N],e[2][N];
ll d[2][N],ans[N];
void dijkstra(int s,ll *dis,const std::vector<int> *e) {
    for(int i=1;i<=n;i++) dis[i]=INF;dis[s]=0;
    std::priority_queue<P,std::vector<P>,std::greater<P> > q;
    q.push(P(0,s));
    while(!q.empty()) {
        P u=q.top();q.pop();
        if(dis[u.second]<u.first) continue;
        for(int i=0;i<g[u.second].size();i++) {
            int v=g[u.second][i],w=e[u.second][i];
            if(dis[v]>dis[u.second]+w) {
                dis[v]=dis[u.second]+w;
                q.push(P(dis[v],v));
            }
        }
    }
}
int main() {
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,a,b;
    while(m--) {
        scanf("%d%d%d%d",&u,&v,&a,&b);
        g[u].push_back(v);e[0][u].push_back(a);e[1][u].push_back(b);
        g[v].push_back(u);e[0][v].push_back(a);e[1][v].push_back(b);
    }
    dijkstra(s,d[0],e[0]);dijkstra(t,d[1],e[1]);
    ans[n]=0;
    for(int i=n-1;~i;i--) ans[i]=std::max(ans[i+1],tot-d[0][i+1]-d[1][i+1]);
    for(int i=0;i<n;i++) printf("%lld\n",ans[i]);
    return 0;
}


Measured memory_bytes: 20736
#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int> > v;
vector<bool> used;

void rec(int n, vector<int> a){
    if(n == 0){
        v.push_back(a);
        return;
    }
    for(int i=0;i<N;i++){
        if(!used[i]){
            a.push_back(i+1);
            used[i] = true;
            rec(n-1, a);
            a.pop_back();
            used[i] = false;
        }
    }
    return;
}

int main(){
    cin >> N;
    vector<int> P(N), Q(N);
    for(int i=0;i<N;i++){
        cin >> P[i];
    }
    for(int i=0;i<N;i++){
        cin >> Q[i];
    }
    used.resize(N, false);
    rec(N,{});
    int a, b;
    for(int i=0;i<int(v.size());i++){
        if(v[i] == P) a = i;
        if(v[i] == Q) b = i;
    }
    cout << abs(a-b) << endl;
    return 0;
}

Measured memory_bytes: 3256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  double n;
  cin>>n;
  vector<double> v(n);
  rep(i,n) cin>>v[i];
  sort(v.begin(), v.end(), greater<double>());
  
  double res = 0, div = 1;
  rep(i,n-1)
  {
    div*=2;
    res += v[i]/div;
  }
  res += v[n-1]/div;
  
  
  cout << setprecision(10) << res << endl;
  
  
  
  return 0;
}
  

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#include<iostream>

using namespace std;
typedef unsigned int ll;

#define REP(i,n) for(ll i=0;i<n;i++)
#define MOD 1000000007 //10^9+7:合同式の法


ll s[2001],t[2001],dp[2001][2001]={0};

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    REP(i,n){cin>>s[i];dp[i][0]=1;}
    dp[n][0]=1;
    REP(i,m){cin>>t[i];dp[0][i]=1;}
    dp[0][m]=1;
    REP(i,n){
        REP(j,m){
            if(s[i]==t[j]){
                dp[i+1][j+1]+=(dp[i+1][j]+dp[i][j+1])%MOD;
            }else{
                dp[i+1][j+1]+=(dp[i+1][j]+dp[i][j+1]-dp[i][j]+MOD)%MOD;
            }
        }
    }
    cout<<dp[n][m]<<"\n";
}

Measured memory_bytes: 19144
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
int n,p[200000];
int main(){
    cin >> n;
    FOR(i,1,n + 1)
        cin >> p[i];

    int m = 0;
    FOR(i,1,n){
        if(p[i] == i && p[i + 1] == i + 1){
            swap(p[i],p[i + 1]);
            m++;
        }
    }
    FOR(i,1,n){
        if(p[i] == i || p[i + 1] == i + 1){
            swap(p[i],p[i + 1]);
            m++;
        }
    }
    cout << m  << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll G[2000][4];
ll Gz[4001][4001];

int main()
{
	int n;
	cin >> n;
	vector<ll> x,y;
	for(int i = 0;i<n;i++)
	{
		for(int j =0;j<4;j++)
		{
			cin >> G[i][j];
			if(j%2)y.push_back(G[i][j]);
			else x.push_back(G[i][j]);
		}
	}
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	//cout<<endl;
	//for(auto i:x)cout<<i<<' ';cout<<endl;
	//for(auto i:y)cout<<i<<' ';cout<<endl;
	//cout<<x.size()<<' '<<y.size()<<endl;
	for(int i = 0;i<n;i++)
	{
		int xl,xu,yl,yu;
		xl = lower_bound(x.begin(),x.end(),G[i][0])-x.begin();
		yl = lower_bound(y.begin(),y.end(),G[i][1])-y.begin();
		xu = upper_bound(x.begin(),x.end(),G[i][2])-x.begin();
		yu = upper_bound(y.begin(),y.end(),G[i][3])-y.begin();
		//cout<<xl<<' '<<yl<<' '<<xu<<' '<<yu<<endl;
		xu--;
		yu--;
		Gz[yl][xl]++;
		Gz[yl][xu]--;
		Gz[yu][xl]--;
		Gz[yu][xu]++;
	}
	for(int i =0;i<n*3;i++)
	{
		for(int j = 0;j<n*3;j++)
		{
			//cout<<Gz[i][j];
		}
		//cout<<endl;
	}
	for(int i = 0;i<n*2;i++)
	{
		for(int j = 0;j<n*2;j++)
		{
			Gz[i+1][j] += Gz[i][j];
		}
	}
	for(int i = 0;i<n*2;i++)
	{
		for(int j = 0;j<n*2;j++)
		{
			Gz[i][j+1] += Gz[i][j];
		}
	}
	ll ans = 0;
	for(int i = 0;i<n*2;i++)
	{
		for(int j = 0;j<n*2;j++)
		{
			//cout<<Gz[i][j];
			if(Gz[i][j])
			{
				
				ans += (y[i+1]-y[i])*(x[j+1]-x[j]);
			}
		}
			//cout<<endl;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 128368
#include <bits/stdc++.h>
#define inf 8000000000000000000LL
using namespace std;
int T,a,b,c,d;
long long n;
map<long long,long long> mp;
long long solve(long long x)
{
    if (mp.find(x)!=mp.end()) return mp[x];
    if (x<=1LL) return 1LL*x*d;
    long long res=inf;
    if (x%2==0) 
    {
        if (solve(x/2)<=inf) res=min(res,solve(x/2)+a);
    }
    else if (x%2==1) 
    {
        if (solve(x/2)<=inf) res=min(res,solve(x/2)+a+d);
        if (solve((x+1)/2)<=inf) res=min(res,solve((x+1)/2)+a+d);
    }
    if (x%3==0) 
    {
        if (solve(x/3)<=inf) res=min(res,solve(x/3)+b);
    }
    else if (x%3==1) 
    {
        if (solve(x/3)<=inf) res=min(res,solve(x/3)+b+d);
    }
    else if (x%3==2) 
    {
        if (solve((x+1)/3)<=inf) res=min(res,solve((x+1)/3)+b+d);
    }
    if (x%5==0) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c);
    }
    else if (x%5==1) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c+d);
    }
    else if (x%5==2) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c+d+d);
    }
    else if (x%5==3) 
    {
        if (solve((x+2)/5)<=inf) res=min(res,solve((x+2)/5)+c+d+d);
    }
    else if (x%5==4) 
    {
        if (solve((x+1)/5)<=inf) res=min(res,solve((x+1)/5)+c+d);
    }
    if (x<=res/d) res=1LL*x*d;
    mp[x]=res;
    return res;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        mp.clear();
        scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);
        printf("%lld\n",solve(n));
    }
    return 0;
}

Measured memory_bytes: 4460
n, k = map(int, input().split())
A = list( map(int, input().split()))
F = list( map(int, input().split())) 
A = sorted(A)
F = sorted(F, reverse = True)

def isok(ans):
    k_ = 0
    for a,f in zip(A,F):
        if a > ans//f:
            k_ += a - ans//f
            if k_ > k:
                return False
    return True

ok = max(A)*max(F)
ng = -1 # -1にしとけば答えが0の時も普通に扱えるな

while ok - ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)

Measured memory_bytes: 121164
import sys

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    ss=readline().strip()
    n=0
    a=100000000
    z=0
    for s in ss:
        if s=="A":
            a=min(a,n)
        elif s=="Z":
            z=n
        n+=1
    print(z-a+1)
    return


resolve()


Measured memory_bytes: 3512
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>

constexpr double f(size_t n){
    return 0.5 * n * (1 + n) / n;
}

int main(){

    size_t n, k;
    std::cin >> n >> k;

    std::vector<double> p, v;

    v.emplace_back(0.0); //累積和

    for(size_t i = 0; i < n; i++){
        size_t tmp;
        std::cin >> tmp;
        p.emplace_back(f(tmp));

        v.emplace_back(v[i] + p[i]);
    }

    double max = 0.0;
    for(size_t i = 0; i + k <= n; i++){
        max = std::max(max, v[i + k] - v[i]);
    }

    std::printf("%.6f\n", max);

    return 0;
}


Measured memory_bytes: 3564
import sys

s = sys.stdin.readline().rstrip()
k = int(sys.stdin.readline())

num=0
cnt1=0
for c in s:
    if c =='1':
        cnt1 +=1
    else:
        num = c
        break
#print(cnt1, num)

if k<=cnt1:
    print(1)
else:
    print(num)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+7;
int cnt[maxn],n,a[maxn];
long long ans;

long long c(int x)
{
	if(x==0) return 0;
	return 1ll*x*(x-1)/2;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;++i) {
		ans+=c(cnt[i]);
	}
	for(int i=1;i<=n;++i) {
		ans-=c(cnt[a[i]]);
		ans+=c(cnt[a[i]]-1);
		printf("%lld\n",ans);
		ans+=c(cnt[a[i]]);
		ans-=c(cnt[a[i]]-1);
	}
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;

signed main () {
	int n, m;
	cin >> n >> m;
	vector < int > h(n + 1, 0);
	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	vector < vector < int > > adj(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector < bool > good(n + 1, 1);
	for (int u = 1; u <= n; ++u) {
		for (int v: adj[u]) {
			if (h[v] >= h[u])
				good[u] = 0;
		}
	}
	cout << count(good.begin(), good.end(), 1) - 1 << '\n';
}


Measured memory_bytes: 8808
import math
import sys
input = sys.stdin.readline

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

N = int(input())
A = list(map(int, input().split()))

mod = 10**9 + 7
# A全体の最小公倍数
a_lcm = 1
for a in A:
    a_lcm = lcm(a_lcm, a)

# Bの総和
b_sum = 0
for i in range(N):
    b_sum += a_lcm // A[i]

print(b_sum % mod)


Measured memory_bytes: 75092
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
////////////////////////////////////////////////////////////////////
int main()
{
    int n; cin >> n;
    vector<int> h(n);
    ll res=0, ans=0;
    REP(i,n){
        cin >> h[i];
        if(h[i]>res) res = h[i];
        if(h[i]>=res) ans++; 
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=[]
B=[]
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
A.sort()
B.sort()
def median(x):
  l=len(x)
  if l%2==0:
    return (x[l//2-1]+x[l//2])/2
  else:
    return x[l//2]
if N%2==1:
  print(median(B)-median(A)+1)
else:
  print(int((median(B)-median(A))*2+1))

Measured memory_bytes: 25460
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      
		int N = sc.nextInt();
      	int count = 0;
      	
      	for(int i = 1; i < N + 1; i ++){
        	int j = sc.nextInt();
        	if(i%2 == 1 && j%2 == 1){
           		count ++;
           }
        }
      	System.out.print(count);
    }
}

Measured memory_bytes: 35780
local read = io.read
local floor = math.floor
local N = read("*n")
local A = {}
for i = 1, N do
	A[i] = read("*n")
end

local possession = 1000
local stock = 0

for i = 1, N do
	if A[i - 1] and A[i - 1] < A[i] then
		possession = possession + stock * A[i]
		stock = 0
	end
	if A[i + 1] and A[i + 1] > A[i] then
		stock = floor(possession / A[i])
		possession = possession % A[i]
	end
end

print(possession)


Measured memory_bytes: 2748
#include "bits/stdc++.h"
using namespace std;

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	int D;
	cin >> D;
	if (D == 25) {
		cout << "Christmas";
		return 0;
	}
	if (D == 24) {
		cout << "Christmas Eve";
		return 0;
	}
	if (D == 23) {
		cout << "Christmas Eve Eve";
		return 0;
	}
	if (D == 22) {
		cout << "Christmas Eve Eve Eve";
		return 0;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>

using namespace std;


int main()
{
	string s; cin >> s;
	int v = 2019 , pow = 1, val = 0;
	int n = s.size();
	map<int,int> m;
	int ans = 0;
	m[0]++;
	for(int i = n-1; ~i; i--){
		int k = s[i]-'0';
		val = (val+(k*pow))%2019;
		ans += m[val];
		m[val]++;
		pow = pow*10%2019;
	}
	cout << ans;
}


Measured memory_bytes: 3728
import java.util.*;
import java.io.*;
class Main{
  public static void main(String args[]){
    StringBuilder bl = new StringBuilder();
    Scanner sc = new Scanner(System.in);

    int max = -1;
    int min = (int)Double.POSITIVE_INFINITY;
    int num = 0;
    int cost = 0;
    int a,s,cur,m;
    int n = sc.nextInt();
    int Array[] = new int[n];
    int C[] = new int[n];
    boolean bool[] = new boolean[n];

    for(int i = 0; i<n; i++){
      num = sc.nextInt();
      Array[i] = num;
      C[i] = num;
      max = Math.max(max,num);
      min = Math.min(min,num);
    }

    quicksort(C,0,n-1);


    List<Integer> Sorted = new ArrayList<Integer>();
    for(int i =0; i<n; i++){
      Sorted.add(C[i]);
    }

    for (int i = 0; i < n; i++) {
      a = 0;
      s = 0;
      cur = i;
      m = max;
      while (true) {
        bool[cur] = true;
        a++;
        int v = Array[cur];
        m = Math.min(m, v);
        s += v;
        cur = Sorted.indexOf(v);
        if (bool[cur]){
          break;
        }
      }
      int cost1 = s + (a - 2) * m;
      int cost2 = s + m + (a + 1) * min;
      cost += Math.min(cost1, cost2);
    }

    System.out.println(cost);
    //printでsort確認
    // for(int i = 0; i < n; i++){
    //   bl.append(' ').append(Array[i]);
    // }
    // bl.append("\n");
    // for(int i = 0; i < n; i++){
    //   bl.append(' ').append(C[i]);
    // }
    // bl.append("\n");
    // System.out.print(bl);

  }
  static int partition(int A[], int p, int r){
    int x = A[r];
    int i = p-1;
    int tmp;
    int s;
    for(int j =p; j<r; j++){
      if(A[j]<=x){
        i = i+1;
        tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
      }
    }
    tmp = A[i+1];
    A[i+1] = A[r];
    A[r] = tmp;
    return i+1;
  }

  static void quicksort(int A[], int p, int  r){
    if(p<r){
      int q = partition(A, p, r);
      quicksort(A, p, q-1);
      quicksort(A, q+1,r);
    }
  }
}


Measured memory_bytes: 32384
///A drunk man will find his way home, but a drunk bird may get lost forever...
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tree<double, null_type, less_equal<double>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
typedef long long ll;
typedef double dd;
typedef long double ldd;
typedef pair <int, int> pii;
typedef pair <pii , int> ppii;
#define pb push_back
#define pf push_front
#define ppb pop_back()
#define ppf pop_front()
#define f first
#define s second
#define sz(x) (int)x.size()
#define smin(x , y) x = min(x , y)
#define smax(x , y) x = max(x , y)
#define mp make_pair
#define all(x) x.begin() , x.end()
#define debug(x) cerr<< #x << " = " << x << endl
#define ddebug(x, y) cerr<< #x << " = " << x  << ", " << #y << " = " << y << endl
#define uop(x, y) pii(min(x, y), max(x, y))
#define mem(a, b) memset(a, b, sizeof a)
#define sq(x) (x) * (x)
#define out return cout << -1 << endl, 0
//const int mx = 1e5 + 10;
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, ans = 0;
	string s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n; i++){
		bool b = 1;
		for(int j = 0; j <= i; j++)
			b &= (s[n - j - 1] == t[i - j]);
		if(b)
			smax(ans , i + 1);
	}
	cout << 2 * n - ans << endl;
	return 0;
}


Measured memory_bytes: 256
//hinagata.cpp
//作成日
//更新日
//目的
//手段
/*includes*/
#include <bits/stdc++.h>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPi(i,a,b) for(ll i=(a);i<(b);i++)
#define REPRi(i,a,b) for(ll i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()

int main(){
    int N;
    cin>>N;
    //input end;
    vector<vector<int>> M(9,vector<int> (9,0));
    REPi(i,1,N+1){
        int matsubi=i%10;
        string S=to_string(i);
        int sentou=S[0]-'0';
        if(matsubi!=0){
            M[sentou-1][matsubi-1]+=1;
        }
    }
    ll count=0;
    REPi(i,1,10){
        REPi(j,1,10){
            count+=M[i-1][j-1]*M[j-1][i-1];
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    visited = [[False] * w for _ in range(h)]
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or visited[y][x] == True or s[y][x] == '#':
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        visited[y][x] = True
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d
                    if (dy != 0 or dx != 0) and dy * dx == 0])
    else:
        print('-1')

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>


using namespace std;

bool isPrime(int n) {
    if (n <= 1) 
        return false; 
  
    for (int i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
} 

int main() {

    

    string days[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string s;
    cin >> s;
    int i;
    for (i=0;i<7;i++) {
        if (s == days[i]) {
            break;
        }
    }
    cout << 7 - i;
    

    return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_t

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 3000;
const int MOD = 1e9+7;

int N;
char s[N_MAX];

int dp0[N_MAX];
int dp1[N_MAX];
int acc[N_MAX + 1];

void solve() {
  auto cur = dp0;
  auto nxt = dp1;
  fill(cur, cur + N, 1);
  REP(k, N - 1) {
    int l = N - 1 - k;
    fill(acc, acc + N + 1, 0);
    FOR(i, 0, l) acc[i + 1] = (acc[i] + cur[i]) % MOD;
    fill(nxt, nxt + N, 0);
    REP(i, l) {
      if (s[k] == '<') {
        nxt[i] = (MOD + acc[i + 1] - acc[0]) % MOD;
      } else {
        nxt[i] = (MOD + acc[l + 1] - acc[i + 1]) % MOD;
      }
    }
    swap(cur, nxt);
  }
  printf("%d\n", cur[0]);
}

void input() {
  scanf("%d", &N);
  scanf("%s", s);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,len,con=0,count=0;
    char a[100];
    scanf("%d",&len);
    getchar();
    for(i=0;i<len;i++)
    {
        scanf("%c",&a[i]);
        if(a[i]=='A')
            con=1;
        else if(a[i]=='B'&&con==1)
            con++;
        else if(a[i]=='C'&&con==2)
            con++;
        else
            con=0;
        if(con==3)
        {
            count++;
            con=0;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<int,P>
#define vpp vector<PP>
#define fi first
#define se second
#define INF 1e9
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    int n,h;
    cin>>n>>h;
    int a=0;
    vi vec(n);
    REP(i,n){
        int t;
        cin>>t>>vec[i];
        a=max(a,t);
    }
    sort(all(vec),greater<int>());
    int ans=0;
    REP(i,n){
        if(h<=0){
            break;
        }
        if(vec[i]>a){
            ans++;
            h-=vec[i];
        }
    }
    ans+=(max(0,h)+a-1)/a;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;

class cards{
    char patt[2];
    int num;
public:
    cards () {}
    void set(char str[]) { patt[0] = str[0]; num = str[1] - '0'; }
    char getPatt() { return patt[0]; }
    int getNum() { return num; }
};

void show(cards C[], int N)
{
    for (int i = 0; i < N; i++) {
        if (i == N - 1)
            cout << C[i].getPatt() << C[i].getNum() << endl;
        else
            cout << C[i].getPatt() << C[i].getNum() << ' ';
    }
}

void bubbleSort(cards C[], int N)
{
    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j >= i + 1; j--)
            if (C[j].getNum() < C[j - 1].getNum())
                swap(C[j], C[j - 1]);
    }
}

void selectionSort(cards C[], int N)
{
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i; j < N; j++)
            if (C[j].getNum() < C[min].getNum())
                min = j;
        swap(C[i], C[min]);
    }
}

int main()
{
    int N;
    char str[3];
    bool chk = true;

    cin >> N;
    cards B[N];
    cards S[N];

    for (int i = 0; i < N; i++) {
        cin >> str;
        B[i].set(str);
        S[i].set(str);
    }
    bubbleSort(B, N);
    selectionSort(S, N);
    show(B, N);
    cout << "Stable" << endl;
    show(S, N);

    for (int i = 0; i < N; i++)
        if (B[i].getPatt() != S[i].getPatt())
            chk = false;
    
    cout << (chk ? "Stable" : "Not stable") << endl;
}


Measured memory_bytes: 3120
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<complex>
#include<bitset>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

struct BIT {
    static const int size = 100100;
    int data[size];

    void add(int a, int x) {
        while (a < size) {
            data[a] += x;
            a += a & -a;
        }
    }

    int sum(int a) {
        int res = 0;
        while (a > 0) {
            res += data[a];
            a -= a & -a;
        }
        return res;
    }
};

int N, M;
pii section[300300];//(長さ,左端)
BIT bit;

signed main() {
    cin >> N >> M;
    rep(i, N) {
        int l, r;
        cin >> l >> r;
        section[i] = pii(r - l + 1, l);
    }
    sort(section, section + N);
    int next = 0;
    for (int d = 1; d <= M; ++d) {
        while (next < N && section[next].first < d) {
            int l = section[next].second;
            int r = l + section[next].first - 1;
            next++;
            bit.add(l, 1);
            bit.add(r + 1, -1);
        }
        int ans = N - next;
        for (int s = 0; s <= M; s += d) {
            ans += bit.sum(s);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 6400
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

toInts :: IO [Int]
toInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

trunc :: Int -> Int -> (Int, Int)
trunc l r = (l, min r (l + 2018))

solver :: Int -> Int -> Int
solver l r =
  if l - r > 2018
    then 0
    else let (l_, r_) = trunc l r
          in minimum [mod (i * j) 2019 | i <- [l_ .. r_], j <- [(i + 1) .. r_]]

main :: IO ()
main = do
  l:r:[] <- toInts
  print $ solver l r

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mk make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define DBG(x) cout << "[" << #x << "]: " << x << endl
using ll = long long;
using pii = pair<int, int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); }
template<class num> inline void rd(num& x) {
	char c, neg = 0; while(isspace(c = getchar_unlocked()));
	if(!isdigit(c)) neg = (c == '-'), x = 0;
	else x = c - '0';
	while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0';
	x = neg ? -x : x; }
template <class... Args> inline void rd(Args&... args) { (rd(args), ...); }

const int MAXN = 2e5 + 5, INF = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	string s, t; cin >> s >> t;

	int n = s.size();
	int m = t.size();
	int ans = 1e9;
	for (int i = 0; i < n - m + 1; i++) {
		int cur  = 0;
		for (int j = 0; j < m; j++) {
			cur += t[j] != s[i+j];
		}
		ans = min(ans, cur);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 3700
#include<stdio.h>
int main(){
	int A,B,C,cin=0,i,day=0;
	scanf("%d%d%d",&A,&B,&C);
	while(cin<C){
		cin+=A;
		day++;
		if(day%7==0)cin+=B;
	}
	printf("%d\n",day);
	return 0;
}



Measured memory_bytes: 2140
#include <stdio.h>
int main(){
  long k,a,b;
  scanf("%ld%ld%ld",&k,&a,&b);
  if (b-a<3 || a>k-1){
    printf("%ld\n",k+1);
  }
  else {
    printf("%ld\n",a+(k-a+1)/2*(b-a)+(k-a+2)/2-(k-a+1)/2);
  }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
int rd()
{
    int sum = 0;char c = getchar();bool flag = true;
    while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}
    while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();
    if(flag) return sum;
    else return -sum;
}
int prime[1010000];
bool flag[1010000];
int main()
{
	int a = rd(),b = rd(),c = rd();
	int ans = b;
	ans += min(c,b);c -= b;
	if(c>0) ans += min(a,c),c -= a;
	if(c>0) ans++;
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch Sequence | diff Sequence.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address Sequence.cpp && ./a.out

/*
 
 5/14/2020
 
 21:47-
 
 */

const int MAX_N=1e6+1;
LL A[MAX_N];
int N;

LL f(bool s) {
  LL cur=0,res=0;
  REP(i,N) {
    int sign=((i%2)^s)?1:-1;
    cur+=A[i];
    if(sign>0) {
      if(cur<sign) res+=sign-cur,cur=sign; 
    } else {
      if(cur>sign) res+=cur-sign,cur=sign;
    }
  }
  return res;
}

void solve() {
  LL res=min(f(0),f(1));
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N;
  REP(i,N) cin>>A[i];
  solve();
  
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>

// limit
#define oo 1000000007LL
#define OO 1000000000000000007LL

// loop
#define fto(i, x, y) for(int i = (x); i <= (y); ++i)
#define fdto(i, x, y) for(int i = (x); i >= (y); --i)
#define ftoa(i, x, y, a) for(int i = (x); i <= (y); i += a)
#define fdtoa(i, x, y, a) for(int i = (x); i >= (y); i -= a)
#define ftoit(it, var) for (__typeof(var.begin()) it = var.begin(); it != var.end(); ++it)
#define fdtoit(rit, var) for (__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); ++rit)

// debug
#define debug cout << "*" << endl;
#define bug1d(a, x, y) { cout << #a << ": "; fto(_, x, y) cout << a[_] << ' '; cout << endl; }
#define bug2d(a, x, y, u, v) { cout << #a << ": " << endl; fto(i, x, y) {fto(j, u, v) cout << a[i][j] << ' '; cout << endl;}; cout << endl;}
#define bug(a) cout << #a << " = " << a << endl;
#define bug2(a, b) cout << #a << " = " << a << "; "; cout << #b << " = " << b << endl;
#define bug3(a, b, c) cout << #a << " = " << a << "; "; cout << #b << " = " << b << "; "; cout << #c << " = " << c << endl;

// operation
#define mp make_pair
#define pb push_back
#define pf push_front

// structure
#define ii pair<int, int>
#define iii pair<ii, int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

// get value
#define FF first
#define SS second

// data type
#define ll long long
#define ull unsigned long long

// function
#define lb lower_bound
#define ub upper_bound

using namespace std;

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T min(T a, T b, T c, T d) {
    return min(a, min(b, min(c, d)));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

template <class T>
T max(T a, T b, T c, T d) {
    return max(a, max(b, max(c, d)));
}

bool cmp(const ii& a, const ii& b) {return (a.FF > b.FF || (a.FF == b.FF && a.SS >= b.SS));}
ll GCD(ll a, ll b) {return (a%b) ? GCD(b, a%b) : b;}

const string namePro = "tmp";
#define maxN 100007

int a[maxN];
int cnt[maxN];

int main() {
//    #ifndef ONLINE_JUDGE
//        freopen((namePro+".inp").c_str(), "r", stdin);
//        freopen((namePro+".out").c_str(), "w", stdout);
//    #endif // ONLINE_JUDGE

    int n;
    scanf("%d", &n);

    fto (i, 1, n) scanf("%d", &a[i]);
    fto (i, 1, n) {
        ++cnt[a[i]+1];
        if (a[i]) ++cnt[a[i]-1];
        ++cnt[a[i]];
    }

    int ans = 0;
    fto (i, 0, 100005) ans = max(ans, cnt[i]);

    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    rep(i,5) {
        int a; cin >> a;
        if(!a) cout << i + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
int main() {
	//input
	int n,rec=0;
	int d[50];
	cin >> n;

	rep(i, n) {
		cin >> d[i];
	}
	
	//compute

	rep(k, n-1) {
		for (int j = k + 1; j < n;j++) {
			rec += d[k] * d[j];
		}
	}

	//output
	cout << rec;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int COMMAX = 100000;
const int MOD = 1000000007;
vector<long long> fac, finv, inv;

void InitializePermutation(void){
    fac.push_back(1LL);
    fac.push_back(1LL);
    finv.push_back(1LL);
    finv.push_back(1LL);
    inv.push_back(0LL); //Though 0^(-1) cannot be defined, there should be some number in inv[0]
    inv.push_back(1LL);
    for (int i = 2; i < COMMAX; i++){
        fac.push_back(fac[i-1] * (long long)i % (long long)MOD);
        inv.push_back((long long)MOD - inv[MOD%i] * (long long)(MOD/i) % (long long)MOD);
        finv.push_back(finv[i-1] * inv[i] % (long long)MOD);
    }
}

long long Permutation(int n, int r){
    if (n < r) return 0LL;
    if (n < 0 || r < 0) return 0LL;
    return fac[n] * finv[n-r] % MOD;
}

int main(void){
    int N, K;
    cin >> N >> K;
    vector<vector<int>> G(N, vector<int>());
    vector<bool> visited(N, false);

    int abuf, bbuf;
    for(int i=0; i<N-1; i++){
        cin >> abuf >> bbuf;
        abuf--;
        bbuf--;
        G[abuf].push_back(bbuf);
        G[bbuf].push_back(abuf);
    }

    InitializePermutation();

    queue<int> queG;

    queG.push(0);
    visited[0] = true;

    int res = K;

    while(!queG.empty()){
        int curVertex = queG.front();
        queG.pop();
        int numChildren = 0;
        for(int chiVertex: G[curVertex]){
            if(visited[chiVertex])continue;
            visited[chiVertex] = true;
            numChildren++;
            queG.push(chiVertex);
        }
        if(curVertex == 0){
            res = res * Permutation(K-1, numChildren) % MOD;
        }else{
            res = res * Permutation(K-2, numChildren) % MOD;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 8940
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

constexpr ll Maisu(ll level) { return level == 0 ? 1 : 3 + Maisu(level - 1) * 2; }
constexpr ll Maisus[51] = {
    Maisu(0),  Maisu(1),  Maisu(2),  Maisu(3),  Maisu(4),  Maisu(5),  Maisu(6),  Maisu(7),
    Maisu(8),  Maisu(9),  Maisu(10), Maisu(11), Maisu(12), Maisu(13), Maisu(14), Maisu(15),
    Maisu(16), Maisu(17), Maisu(18), Maisu(19), Maisu(20), Maisu(21), Maisu(22), Maisu(23),
    Maisu(24), Maisu(25), Maisu(26), Maisu(27), Maisu(28), Maisu(29), Maisu(30), Maisu(31),
    Maisu(32), Maisu(33), Maisu(34), Maisu(35), Maisu(36), Maisu(37), Maisu(38), Maisu(39),
    Maisu(40), Maisu(41), Maisu(42), Maisu(43), Maisu(44), Maisu(45), Maisu(46), Maisu(47),
    Maisu(48), Maisu(49), Maisu(50)};

constexpr ll Putty(ll level) { return level == 0 ? 1 : 1 + Putty(level - 1) * 2; }
constexpr ll Puttys[51] = {
    Putty(0),  Putty(1),  Putty(2),  Putty(3),  Putty(4),  Putty(5),  Putty(6),  Putty(7),
    Putty(8),  Putty(9),  Putty(10), Putty(11), Putty(12), Putty(13), Putty(14), Putty(15),
    Putty(16), Putty(17), Putty(18), Putty(19), Putty(20), Putty(21), Putty(22), Putty(23),
    Putty(24), Putty(25), Putty(26), Putty(27), Putty(28), Putty(29), Putty(30), Putty(31),
    Putty(32), Putty(33), Putty(34), Putty(35), Putty(36), Putty(37), Putty(38), Putty(39),
    Putty(40), Putty(41), Putty(42), Putty(43), Putty(44), Putty(45), Putty(46), Putty(47),
    Putty(48), Putty(49), Putty(50)};

ll calc(ll n, ll x) {
  if (x >= Maisus[n]) {
    return Puttys[n];
  }

  const ll mid = Maisus[n] / 2 + 1;
  if (x <= n) {
    return 0;
  } else if (x < mid) {
    return calc(n - 1, x - 1);
  } else if (x == mid) {
    return Puttys[n - 1] + 1;
  } else {
    return Puttys[n - 1] + 1 + calc(n - 1, x - 2 - Maisus[n - 1]);
  }
}

int main() {
  ll N, X;
  cin >> N >> X;

  const ll ans = calc(N, X);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MOD 1000000007
//逆元保存テーブル
long long inverse_element_table[2001] = { };

//繰り返し自乗法 O(log(n))
long long my_pow(long long a, int n)
{
    long long ret = 1;
    for (; n > 0; n >>= 1) {
        if (n % 2)
            ret *= a;
        ret %= MOD;
        a = a * a % MOD;
    }
    return ret % MOD;
}
//テーブル作成
//フェルマーの小定理より,aと素数pに対してpを法として
// a * pow(a,p-2) ≡ 1 
// よってaの逆元は pow(a,p-2)
// つまり aで割る代わりに pow(a,p-2) をかけてやればいい
// このため 逆元を前処理で生成しておく
// O(log(MOD - 2) * 2000)
void init_table(void)
{
    for (int i = 1; i < 2000; i++) {
        inverse_element_table[i] = my_pow((long long) i, MOD - 2);
    }
}

//O(N)
long long comb(int n, int r)
{
    long long ret = 1;
    for (int i = n - r + 1; i <= n; i++) {
        ret *= i;
        ret %= MOD;
    }
    for (int i = 1; i <= r; i++) {
        //iで割る代わりに逆元かける
        ret *= inverse_element_table[i];
        ret %= MOD;
    }
    return ret;
}

int main(void)
{
    //逆元テーブル生成
    init_table();
    int N, K;
    scanf("%d %d", &N, &K);
    //O(N^2)
    for (int i = 1; i <= K; i++) {
        long long ans = comb(1 + N - K, i) * comb(K - 1, K - i);
        printf("%lld\n", ans % MOD);
    }
}


Measured memory_bytes: 1732
package main

import (
	"fmt"
	"sort"
)

func CardGameforTwo(array []int) int {
	sort.Ints(array)
	var AliceV int
	var BobV int
	for len(array) > 1 {
		AliceV += array[len(array)-1]
		BobV += array[len(array)-2]
		array = array[:len(array)-2]
	}
	if len(array) == 1 {
		AliceV += array[0]
	}

	return AliceV - BobV
}

func main() {
	var N int
	fmt.Scan(&N)
	array := []int{}
	for i:=0; i < N; i ++ {
		var value int
        	fmt.Scan(&value)
		array = append(array,value)
	
	}
	fmt.Println(CardGameforTwo(array))
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using str = string;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;

int main() {
    int n;
    cin >> n;

    int a = n % 10;
    if(a == 2 || a == 4 || a == 5 || a == 7 || a == 9) {
        cout << "hon" << endl;
        return 0;
    }
    if(a == 0 || a == 1 || a == 6 || a == 8) {
        cout << "pon" << endl;
        return 0;
    }
    if(a == 3) {
        cout << "bon" << endl;
        return 0;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,maxv=-1e10,minv=1e11+1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		maxv=max(maxv,x);
		minv=min(minv,x);
	}
	cout<<abs(maxv-minv);
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program{
  
  static void Main()
  {
    string[] X=Console.ReadLine().Split(' ');
    int X1=int.Parse(X[0]);
    int X2=int.Parse(X[1]);
    int X3=int.Parse(X[2]);
    int X4=int.Parse(X[3]);
    int X5=int.Parse(X[4]);

    
    if(X1==0)
    {
      Console.WriteLine("1");
    }
    else if(X2==0)
    {
      Console.WriteLine("2");
    }
    else if(X3==0)
    {
      Console.WriteLine("3");
    }
    else if(X4==0)
    {
      Console.WriteLine("4");
    }
    else if(X5==0)
    {
      Console.WriteLine("5");
    }
  }
  
}

Measured memory_bytes: 27532
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

ll W,w1;
mat x(5);
int S[4][110];
int ans=0;
void func(int s,ll w,int v){
    if(s==4){
        if(w<=W)ans=max(ans,v);
        return;
    }
    for(int i=0;i<=x[s].size();i++){
        ll p=w;int q=v;
        p+=(ll)i*(ll)(w1+s);
        q+=S[s][i];
        if(p>W)continue;
        func(s+1,p,q);
    }
}

int main(){
    int N;cin>>N>>W;
    int v1;cin>>w1>>v1;
    x[0].push_back(v1);
    ll w;int v;
    for(int i=2;i<=N;i++){
        cin>>w>>v;
        x[w-w1].push_back(v);
    }
    sort(x[0].begin(),x[0].end(),greater<int>());
    sort(x[1].begin(),x[1].end(),greater<int>());
    sort(x[2].begin(),x[2].end(),greater<int>());
    sort(x[3].begin(),x[3].end(),greater<int>());
    
    S[0][0]=S[1][0]=S[2][0]=S[3][0]=0;
    for(int i=0;i<4;i++){
        for(int j=1;j<=x[i].size();j++)
            S[i][j]=S[i][j-1]+x[i][j-1];
    }
    func(0,0,0);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
/*author : Yashvardhan
Sunday, May 10, 2020
5:32 PM
*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define vpi vector<pi>
#define ff first
#define ss second
#define mp make_pair
#define endl '\n'
#define all(a) a.begin(), a.end()
#define initialise(a, x) memset(a, x, sizeof(a))
#define rev(Y) reverse(all(Y))

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#ifdef __APPLE__
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << "  ";
	__f(comma + 1, args...);}
#else
#define debug(...)
#endif

template <typename T> ostream& operator << (ostream& os,const vector<T>& v){for(int i=0;i<v.size();++i) os<<v[i]<<" ";return os;} 
template <typename T> ostream& operator << (ostream& os,const set<T>& v){for(auto it:v) os<<it<<" ";return os;} 
template <typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {os<<v.ff<<" "<<v.ss;return os;}

const int mod = 1e9 + 7;
const int inf = 2e18;
const int ninf = -2e18;

int takemod(int a){return ((a%mod)+mod)%mod;}

int pow(int a, int b, int m)
{
	int ans = 1;
	a %= m;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int a){return takemod( pow( takemod(a), mod-2,mod ) );}


signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	#ifdef __APPLE__
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("error.txt","w",stderr);
	#endif

	time_t t1, t2;
	t1 = clock();
	
	int a,b,c,k;
	cin >> a >> b >> c >> k;

	int ans = 0;
	vi arr = {a,b,c};
	vi mul = {1,0,-1};

	for(int i = 0; i < 3; i++){
		if(k <= 0) break;
		ans += (mul[i]) * min(arr[i],k);
		k -= arr[i];
	}
	cout << ans << endl;

	t2 = clock();
	cerr << endl << t2-t1 << endl;
	
	return 0;
}



Measured memory_bytes: 3680
#include "bits/stdc++.h"

using namespace std;

typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

struct UnionFind {
	vector< int > data;

	UnionFind(int sz) {
		data.assign(sz, -1);
	}

	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return (false);
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return (true);
	}

	int find(int k) {
		if (data[k] < 0) return (k);
		return (data[k] = find(data[k]));
	}

	int size(int k) {
		return (-data[find(k)]);
	}
};

signed main(){

	struct Town{
		int i, x, y;
	};
	struct Diff{
		int d, i, j;
	};

	vector<Town> v;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++){
		int x, y;
		cin >> x >> y;
		v.push_back({ i, x, y });
	}

	UnionFind u(N);
	vector<Diff> vd;

	sort(v.begin(), v.end(), [](Town& a, Town& b){ return a.x < b.x; });
	Town pre = v[0];
	for (int i = 1; i < N; i++){
		Town now = v[i];
		vd.push_back({min(abs(now.x-pre.x), abs(now.y-pre.y)), pre.i, now.i});
		pre = now;
	}
	sort(v.begin(), v.end(), [](Town& a, Town& b){ return a.y < b.y; });
	pre = v[0];
	for (int i = 1; i < N; i++){
		Town now = v[i];
		vd.push_back({ min(abs(now.x - pre.x), abs(now.y - pre.y)), pre.i, now.i });
		pre = now;
	}

	sort(vd.begin(), vd.end(), [](Diff& a, Diff& b){return a.d < b.d; });

	int ans = 0;
	for (auto d : vd){
		if (u.unite(d.i, d.j)){ N--; ans += d.d; }
		if (N == 1) break;
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 11632
#!/usr/bin/env python3
import sys
import math

line = sys.stdin.readline().strip()
N = int(line)
line = sys.stdin.readline().strip()
A = [int(x) for x in line.split()]

m = 2 << 31-1
for a in A:
    m = min(m, a & -a)
print(len(bin(m))-3)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

int main ()
{
    int N;cin>>N;
    vector<int> h(N);
    REP(i,N) cin>>h[i];
    vector<int> cost(N,0);
    for(int i = 1; i < N; i++)
    {   int tcost;
        if (i>1){
            int cost_1 = cost[i-1] + abs(h[i] - h[i-1]);
            int cost_2 = cost[i-2] + abs(h[i] - h[i-2]);
            tcost =min(cost_1,cost_2);
        }else{
            tcost = cost[i-1] + abs(h[i] - h[i-1]);
        }
        cost[i] = tcost;
    }
    cout<<cost[N-1]<<endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int A[101010],B[101010];

int main(){
  int N; cin>>N;
  vector<pair<ll,int>> V(N);
  rep(i,N){
    cin>>A[i]>>B[i];
    V[i]={1LL*A[i]+1LL*B[i],i};
  }
  sort(V.rbegin(),V.rend());
  ll ans=0;
  rep(i,N){
    int j=V[i].second;
    if(i%2==0) ans+=1LL*A[j];
    else ans-=1LL*B[j];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 2560
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int a, b, c;
  cin >> a >> b >> c;
  if (a + b > c && b + c > a && c + a > b && a == b && b == c) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 888