akhauriyash/Code-Regression huggingface dataset:
///============================================================================
/// Name        : Faisal.cpp
/// Author      : Faisal Ahmed
/// Version     :
/// Copyright   : Your copyright notice
/// Description : C++, Ansi-style
///============================================================================

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef long double ld;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, arr[110];

	cin >> n;
	for(int i = 0; i < n; i++){
        cin >> arr[i];
	}

    int ans = INT_MAX;
	for(int i = 0; i < n; i++){
        int s1 = 0, s2 = 0;
        for(int j = 0; j <= i; j++){
            s1 += arr[j];
        }
        for(int j = i + 1; j < n; j++){
            s2 += arr[j];
        }
        ans = min(ans, abs(s1 - s2));
	}

	cout << ans << endl;

	return 0;
}



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

#define int long long
#define double long double

const int INF = 9223372036854775807;

struct line{
    int a, b;
};

vector< line > convexHull;

double intersect(line a, line b){
    if(a.a == b.a) return -INF;
    return ((double)(b.b-a.b)/(double)(a.a-b.a));
}

int query(int x){
    int l = 0;
    int r = convexHull.size()-1;

    if(convexHull.empty()) return INF;

    while(l < r){
        int mid = (l+r)/2;

        int tmp = convexHull[mid].b+convexHull[mid].a*x;
        int tmp1 = convexHull[mid+1].b+convexHull[mid+1].a*x;

        if(tmp < tmp1){
            r = mid;
        }else{
            l = mid+1;
        }

    }

    return convexHull[l].b+convexHull[l].a*x;
}

void add(int a, int b){
    line c;
    c.a = a;
    c.b = b;

    while(convexHull.size() >= 2 && intersect(convexHull[convexHull.size()-2], c) <= intersect(convexHull[convexHull.size()-2], convexHull.back())){
        convexHull.pop_back();
    }

    convexHull.push_back(c);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, c;
    cin >> n >> c;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }

    int ans = 0;

    add(-2*v[0],v[0]*v[0]);

    for(int i = 1; i < n; i++){

        ans = c+v[i]*v[i]+query(v[i]);

        add(-2*v[i], ans+v[i]*v[i]);

    }

    cout << ans << endl;
}


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

int main() {
  int N, A , B;
  
  cin >> N >> A >> B ;
  
  int P1 = A*N;
  int P2 = B;

  if(P1 <= P2 ){
    cout << P1 << endl;
  }
  else{
    cout << P2 << endl;
  }

  // ここにプログラムを追記
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int N;
int p[111111]={1,1};
vector<int>v;
int main(){
    for(int i=2;i<111111;i++)
        if(!p[i])
            for(int j=2;i*j<111111;j++)
                p[i*j]++;
    for(int i=1;i<111111;i+=2){
        if(!p[i]&&!p[i/2+1])
            v.push_back(i);
    }
    cin>>N;
    while(N--){
        int x,y;
        cin>>x>>y;
        cout<<(int)(upper_bound(v.begin(),v.end(),y)
        -lower_bound(v.begin(),v.end(),x))
        <<'\n';
    }
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
//#include <iomanip>
using namespace std;

int main(){

	int n;
	cin >> n;

	for(int i = 1; i < n + 1; i++){
		if(i % 3 == 0){
			cout << " " << i;
		}else{
			int x = i;
			while(x){
				if(x % 10 == 3){
					cout << " " << i;
					break;
				}
				x /= 10;
			}
		}
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,-1};
const int dy[6] = {0, 1, 0, -1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------


int main(){
    int A,B,C;
    cin >> A >> B >> C;
    int week = A*7+B;
    int ans = (C/week)*7;
    C = C%week;
    if(C){
        ans += min(7,(C+A-1)/A);
    }
    cout << ans << enld;
    return 0;
}


Measured memory_bytes: 3096
import numpy as np
N = int(input())
A = np.int32(input().split())
B = np.int32(input().split())

ans = 0
for k in range(29):
    a = np.sort(A%(2**(k+1)))
    b = B%(2**(k+1))
    ans += (np.sum(np.searchsorted(a,2**(k+1)-b)-np.searchsorted(a,2**k-b)+N-np.searchsorted(a-2**(k+1),2**k-b)))%2*2**k

print(ans)

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;};
void qmod(ll &a,ll b){a=(a*b)%MOD;};
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x, ll y, ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}   


int main(){
  ll i,j,o;
  ll result=0,buf=0,buf1=0,buf2=0,buf3=0,buf4=0;
  bool judge = true;
  string s;cin>>s;
  ll a=s[0]-'0',b=s[1]-'0',c=s[2]-'0',d=s[3]-'0';
  char p[3];
  bitset<3> k;
  for(i=0;i<(1<<3);i++){
    k=i;
    buf=s[0]-'0';
    for(j=0;j<3;j++){
      if(k[j]==true){buf+=s[j+1]-'0';p[j]='+';}
      else{buf-=s[j+1]-'0';p[j]='-';}
    }
    //cout<<buf<<endl;
    if(buf==7)break;
  }
  cout<<s[0]<<p[0]<<s[1]<<p[1]<<s[2]<<p[2]<<s[3]<<"=7"<<endl;



  return 0;
}

Measured memory_bytes: 256
n = int(input())
b = list(map(int, input().split()))
a = [0] * n
a[0] = b[0]
for i in range(1,n-1):
  a[i] = min(b[i], b[i-1])
a[n-1] = b[n-2]
ans = sum(a)
print(ans)
  
  

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception{
        
      Scanner s = new Scanner(System.in);
        String input = s.nextLine();
      
      boolean isSame = String.valueOf(input.charAt(0)).equals(String.valueOf(input.charAt(1))) &&
        				String.valueOf(input.charAt(1)).equals(String.valueOf(input.charAt(2)));
   
    	System.out.println(isSame ? "No" : "Yes");
    }
}

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF 2000000000000000000LL
#define EPS 1e-9
#define debug(a) cerr<<#a<<"="<<(a)<<"\n"
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 1e9+7;
const double PI = acos(-1);

int n,i,j,k,t;
double dp[301][301][301];
bool vis[301][301][301];
int a[304];
int cnt[4];

double solve(int c3, int c2, int c1){
    double &ans = dp[c3][c2][c1];
    if(!vis[c3][c2][c1]){
        vis[c3][c2][c1] = true;
        int sum = c3+c2+c1;
        ans = 1.0*n/sum;
        if(sum){
            if(c3)
                ans += 1.0*c3/sum *(solve(c3-1, c2+1, c1));
            if(c2)
                ans += 1.0*c2/sum *(solve(c3, c2-1, c1+1));
            if(c1)
                ans += 1.0*c1/sum *(solve(c3, c2, c1-1));
        }
    }
    return ans;
}

int main(){
    memset(cnt, 0, sizeof cnt);
    memset(vis, false, sizeof vis);
    scanf("%d", &n);
    for(i=0;i<n;++i){
        scanf("%d", a+i);
        cnt[a[i]]++;
    }
    vis[0][0][0] = true;
    dp[0][0][0] = 0;
    printf("%.9lf\n", solve(cnt[3], cnt[2], cnt[1]));
    return 0;
}

Measured memory_bytes: 240000
import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    temp = n // 2
    for i in prime:
        if i > temp:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)

Measured memory_bytes: 7236
//According to all known laws of aviation, there is no way that a bee should be able to fly.
 //Its wings are too small to get its fat little body off the ground. The bee, of course, flies anyway.
 //Because bees don't care what humans think is impossible.
 #include <bits/stdc++.h>
 #define FAST_IO  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 #define mod 1000000007
 #define endl "\n"
 using namespace std ;
 using bigint = long long int ;
 using vi = vector<int> ;
 using vll = vector<bigint> ;
vll v ;
void lunlunNumbergenerator( bigint N ){
    if( N > 1e11 )
        return ;
    v.push_back(N) ;
    int d = N % 10 ;
    if( d == 0 ){
        lunlunNumbergenerator(N*10+1) ;
        lunlunNumbergenerator(N*10) ;
    }
    else if( d == 9 ){
        lunlunNumbergenerator(N*10+d) ;
        lunlunNumbergenerator(N*10+d-1) ;
    }
    else if( d == 1 ){
        lunlunNumbergenerator(N*10) ;
        lunlunNumbergenerator(N*10+1) ;
        lunlunNumbergenerator(N*10+2) ;
    }
    else{
        lunlunNumbergenerator(N*10+d-1) ;
        lunlunNumbergenerator(N*10+d+1) ;
        lunlunNumbergenerator(N*10+d) ;
    }
}
 
 int main(){
     for( bigint i = 1 ; i < 10 ; i++ )
         lunlunNumbergenerator(i) ;
     sort( v.begin() , v.end()) ;
     int N ; cin >> N ;
     cout << v[N-1] << endl ;
     return 0 ;
 }

Measured memory_bytes: 11496
#include<bits/stdc++.h>
#define LL long long
#define MAXN 200005
using namespace std;

int N,K;
int a[MAXN];
LL s[MAXN], c[MAXN];
//
int fw[MAXN];
int lbt(int x){
	return x & (-x);
}

void update(int x, int dv){
	for(;x<=N;x+=lbt(x)){
		fw[x] += dv;
	}
}

int getsum(int x){
	int ans = 0;
	for(;x>0;x-=lbt(x)){
		ans += fw[x];
	}
	return ans;
} 


int main(){
	
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		cin>>a[i];
		a[i] -= K;
		
		s[i] = s[i-1] + a[i];
	}
	
	memcpy(c, s, sizeof(s));
	sort(c+1, c+1+N);
	
	LL ans = 0;

	for(int i=1;i<=N;i++){
		if(s[i]>=0) ++ans;
		
		s[i] = lower_bound(c+1, c+1+N, s[i]) - c;
		ans += getsum(s[i]);
		update(s[i], 1);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 4992
n = int(input())
T = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
M = []

for i in range(n):
    M += [V[i]]*T[i]*2
   
M = [min(v1, v2) for v1, v2 in zip([0] + M, M + [0])]



for i in range(1,len(M)):
    M[i] = min(M[i],M[i-1]+0.5)
    
for i in range(len(M)-2,0,-1):
    M[i] = min(M[i],M[i+1]+0.5)
    
ans = 0
for i in range(1,len(M)):
    ans += 0.5*(M[i]+M[i-1])*0.5

print(ans)

Measured memory_bytes: 4400
#include <stdio.h>

/*
????¨?
?§???????????????? SS ???????????????????????§???hh:mm:ss ?????¢?????????????????????????????????????????????????????§???hh ????????????mm ??? 60 ???????????????ss ??? 60 ??????????§???¨????????????

Input
SS ???1???????????????????????????

Output
hh???mm???ss ??? :(?????????)???????????§1???????????????????????????????????°??????1????????´??????0 ????????????2?????¨???????????????????????????????????????

*/

int main( void )
{
    int ss, iH, iM ,iS;

    scanf( "%d", &ss );

	iS = ss % 60;
	ss = ( ss - iS ) / 60;
	
	iM = ss % 60;
	ss = ( ss - iM ) / 60;
	
	iH = ss;

    printf( "%d:%d:%d\n", iH, iM, iS );

    return 0;
}

Measured memory_bytes: 592
n = int(input())
a = list(map(int, input().split()))
Ans = [0 for i in range(n)]
for i in range(1,n + 1)[::-1]:
    count = 0
    mul = 1
    k = i
    while k * mul <= n:
        count += Ans[k * mul - 1]
        mul += 1
    if count % 2 != a[i - 1]:
        Ans[i - 1] = 1
print(sum(Ans))
for i in range(1, n + 1):
    if Ans[i - 1] == 1:
        print("{} ".format(i), end = " ")

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

using namespace std;

long long p[100005], q[100005], r[100005];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	long long x, y, a, b, c, c1, br = 0;
	cin >> x >> y >> a >> b >> c;
	c1 = c;
	for(long long i = 0; i < a; ++i) cin >> p[i];
	for(long long i = 0; i < b; ++i) cin >> q[i];
	for(long long i = 0; i < c; ++i) cin >> r[i];
	sort(p, p + a);
	sort(q, q + b);
	sort(r, r + c);
	reverse(p, p + a);
	reverse(q, q + b);
	--x;
	--y;
	--c;
	while((x >= 0 or y >= 0) and c >= 0){
//		cout << p[x] << " " << q[y] << " " << r[c] << endl;
        if(x < 0){
        	if(q[y] < r[c]){
				--y;
				--c;
			}
			else break;
			continue;
		}
		if(y < 0){
			if(p[x] < r[c]){
				--x;
				--c;
			}
			else break;
			continue;
		}
		if(p[x] < q[y]){
			if(p[x] < r[c]){
				--x;
				--c;
			}
			else break;
		}
		else{
			if(q[y] < r[c]){
				--y;
				--c;
			}
			else break;
		}
	}
	for(long long i = 0; i <= x; ++i) br += p[i];
//	cout << br << endl;
	for(long long i = 0; i <= y; ++i) br += q[i];
//	cout << br << endl;
	for(long long i = c + 1; i < c1; ++i) br += r[i];
	cout << br;

	return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std ;
int main () {
string s,ss;
cin >>s>>ss ;
bool ok= 0 ;
int len=s.size();
for ( int i=0;i<len;++i)
    {
if (s==ss) {
ok=1 ;
break ;
}

s = s.back()+s.substr(0,len-1);
}
if ( ok )
    {
cout<<"Yes"<<endl;
}

else{
cout<<"No"<<endl;
}
return 0;
}

Measured memory_bytes: 256
import itertools

X = int(input())

ansL1 = [i for i in range(130)]
ansL2 = [i * (-1) for i in range(1, 130)]
ansL1.extend(ansL2)

L1 = [pow(i, 5)for i in range(130)]
L2 = [pow((-1)*i, 5)for i in range(1, 130)]
L1.extend(L2)

for v in itertools.combinations(L1, 2):
    if v[0] - v[1] == X:
        for i in range(len(L1)):
            if v[0] == L1[i]:
                ans1 = ansL1[i]
            if v[1] == L1[i]:
                ans2 = ansL1[i]
        print(ans1, ans2)
        exit()


Measured memory_bytes: 9224
#include<iostream>
using namespace std;
int main(){
int a[100]={};
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}

for(int i=0;i<n;i++){
int key=a[i];
int j=i-1;
while(j>=0 && a[j]>key){
	a[j+1]=a[j];
	j--;
}
a[j+1]=key;
for(int i=0;i<n;i++){
if(i!=n-1)
cout<<a[i]<<" ";
else
cout<<a[i]<<endl;
}
}
}



Measured memory_bytes: 3096
#include<stdio.h>
#define MAX 1000005
#define NIL -1

struct Node{
  int p;
  int l;
  int r;
};

struct Node T[MAX];
int n,D[MAX];

void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p == NIL){
    printf("root, ");
  }
  else if(T[u].l == NIL){
    printf("leaf, ");
  }
  else{
    printf("internal node, ");
  }
    
  printf("[");

  for(i = 0,c = T[u].l;c!=NIL;i++,c = T[c].r){
    if(i)printf(", ");

    printf("%d",c);
  }
  printf("]\n");
    }

int rec(int u,int p){
  D[u] = p;
  if(T[u].r != NIL){
    rec(T[u].r,p);
  }
  if(T[u].l!= NIL){
    rec(T[u].l,p+1);
  }
}

int main(){
  int i,j,d,c,v,l=0,r;
  scanf("%d",&n);

  for(i=0 ; i<n ; i++){
    T[i].p = NIL;
    T[i].l = NIL;
    T[i].r = NIL;
  }
    
  for(i = 0;i<n;i++){
    scanf("%d%d",&v,&d);
    for(j = 0;j<d;j++){
      scanf("%d",&c);
        if(j == 0) {T[v].l = c;}
        else{T[l].r = c;}
    l = c;
	T[c].p = v;
    }
  }
    
  for(i=0 ; i<n ; i++){
    if(T[i].p == NIL) r = i;
  }
    
  rec(r,0);
  for(i=0 ; i<n ; i++) print(i);

  return 0;
  
}



Measured memory_bytes: 6404
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef long long LL;

int main() {
	int y, m, d, mm, dd;
	scanf("%d/%1d%1d/%1d%1d", &y, &m, &mm, &d, &dd);
	printf("2018/%d%d/%d%d\n", m, mm, d, dd);
	return 0;
}









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

int main(){
    int n=0;
    cin >> n;
    if(n>100) cout << "n must be smaller than 101";
    string answer = "No";
    for(int i=1; i<10;i++){
	if(n%i == 0){
	    int n_over_i = n/i;
	    for(int j=1; j<10;j++){
		if( n_over_i%j ==0 && (int)(n_over_i/j) ==1 ){
		    //cout << "(int)(n_over_i/j) " << (int)(n_over_i/j) << "\n";
		    answer = "Yes";
		}
	    }
	}
    }
    cout << answer;
    return 0;
}


Measured memory_bytes: 256
/**
Problem Statement

Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.

The vacation consists of  N days. For each
), Taro will choose one of the following activities and do it on the i-th day:
A: Swim in the sea. Gain a_i
 points of happiness.
B: Catch bugs in the mountains. Gain b_i
 points of happiness.
C: Do homework at home. Gain c_i
 points of happiness.
As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.

Find the maximum possible total points of happiness that Taro gains.

*/
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;
int main()
{
    int n;
   cin>>n;
   vector<int> dp(3);
   for(int days=0;days<n;days++)
   {
       vector<int> new_dp(3,0);
       vector<int> c(3);
       for(int i=0;i<3;++i)
       {
           cin>>c[i];
       }

       for(int i=0;i<3;++i)
       {
           for(int j=0;j<3;++j)
           {
               if( i!=j)
               {
                   new_dp[j]= max(new_dp[j],dp[i]+c[j]);
               }
           }
       }
       dp= new_dp;
   }
   cout<<max(dp[0],max(dp[1],dp[2]));
    return 0;
}



Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
    int n,i;
    long long int sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if((i%3)!=0 && (i%5)!=0)
        {
            sum+=i;
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3188
MOD = 998244353
n, a, b, k = map(int, input().split())
pair = []
for x in range(n+1):
    y, r = divmod(k-a*x, b)
    if y < 0:
        continue
    if r == 0:
        pair.append((x, y))


memo = [0]*n


def com(n, r):
    X = Y = 1
    if n < r:
        return 0
    if n-r < r:
        r = n-r
    if r == 0:
        memo[r] = 1
        return memo[r]
    if memo[r] != 0:
        return memo[r]
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
        memo[i] = X*pow(Y, MOD-2, MOD)
    return memo[r]

com(n, n//2)

ans = 0
for x, y in pair:
    ans += com(n, x)*com(n, y) % MOD
print(ans % MOD)


Measured memory_bytes: 50680
/*
ID: taoxiaa1
PROG: lamps
LANG: C++
*/
//URAL ID:248353QC
#include<bits/stdc++.h>
using namespace std;
//FILE *in, *out;
//in = fopen("lamps.in", "r");
//out = fopen("lamps.out", "w");
//ofstream fout("lamps.out");
//ifstream fin("lamps.in");
int s[200005],t[200005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        t[i]=s[i];
    }
    sort(t+1,t+1+n);
    int a=t[n/2];
    for(int i=1;i<=n;i++){
        if(s[i]<=a)cout<<t[n/2+1]<<endl;
        else cout<<a<<endl;
    }
    return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
int gcd(int a,int b)
{
	if(b==0)
	return a;
	
	return gcd(b,a%b);
}
ll power(ll x,ll y)
{
	ll res=1;
	x=x%mod;
	while(y>0)
	{
		if(y&1)
		res=(res*x)%mod;
		
		y=y>>1;
		x=(x*x)%mod;
	}
	return res;
}
struct Matrix{ 
	int a[2][2] = {{0,0},{0,0}};
	Matrix operator *(const Matrix& other){
		Matrix product;
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
						product.a[i][k] =product.a[i][k] + (ll)a[i][j]*other.a[j][k];
				}
			}
		}
		return product;
	}
};
//int modInverse(int n,int p)
//{
	//return power(n,p-2,p);
//}
int main() {
	// your code goes here
	 ios_base::sync_with_stdio(0);
	 cin.tie(0);
	 int n;
	 cin>>n;
	 ll mi1 = 1e12;
	 ll mi2 = 1e12;
	 ll ma2 = -1e12;
	 ll ma1 = -1e12;
	 for(int i=0;i<n;i++)
	 {
		 ll x,y;
		 cin>>x>>y;
		 ll s1 = x+y;
		 ll s2 = x-y;
		 mi1 = min(mi1,s1);
		 ma1 = max(ma1,s1);
		 mi2 = min(mi2,s2);
		 ma2 = max(ma2,s2);
	 }
	 cout<<max(abs(mi1-ma1),abs(mi2-ma2))<<'\n';

	 return 0;
}


Measured memory_bytes: 3488
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct CountUnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;
    vector<int> cnt;

    CountUnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        cnt.assign(sz, 1);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else    return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)  return;
        if(rank[x] < rank[y]){
            par[x] = y;
            cnt[y] += cnt[x];
        }
        else{
            par[y] = x;
            cnt[x] += cnt[y];
            if(rank[x] == rank[y])  ++rank[x];
        }
    }

    int get_cnt(int x){
        return cnt[find(x)];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<P> es;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        es.emplace_back(u, v);
    }
    CountUnionFind uf(n);
    vector<ll> ans(m);
    ans[m - 1] = (ll)n * (n - 1) / 2;
    for(int i = m - 1; i > 0; --i){
        int u = es[i].first, v = es[i].second;
        ans[i - 1] = ans[i];
        if(!uf.same(u, v)){
            int foo = uf.get_cnt(u), bar = uf.get_cnt(v);
            uf.unite(u, v);
            ans[i - 1] -= (ll)foo * bar;
        }
    }
    for(int i = 0; i < m; ++i)  cout << ans[i] << '\n';
}

Measured memory_bytes: 4084
// ABC152_B
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <cstring>  // std::memset
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define repr(i, n) for (ll i=n-1; i >= 0; i++)  // n-1 ~ 0
#define rep1(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define all(vec) (vec).begin(), (vec).end()
#define sum(vec) accumulate(all(vec), 0LL)  // 0 は初期値
#define min_vec(vec) min_element(all(vec))  // iterator: * を先頭につける
#define max_vec(vec) max_element(all(vec))  // iterator: * を先頭につける
#define idx(vec, element_iter) distance((vec).begin(), element_iter)
const ll INF = 1LL<<60;  // 10^18（const int inf = 1<<29;）
const double PI = acos(-1);



int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    // input(sunippets: inpv, inpn, inps)
    ll N, M;
    cin >> N >> M;
    char nn = '0' + N;
    char mm = '0' + M;
    string n, m, res;
    
    // calculation
    rep(i, M) {
        n += nn;
    }
    rep(i, N) {
        m += mm;
    }
    
    res = n <= m ? n : m;
    cout << res << "\n";
    
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int N;
    cin >> N;
    uint64_t A;
    cin >> A;
    bool overflow = false;
    for (int i = 1; i < N; ++i)
    {
        uint64_t A1;
        cin >> A1;
        if (A1 == 0)
        {
            cout << 0 << endl;
            return 0;
        }
        if (A <= ((uint64_t)1000000000000000000 / A1))
        {
            A *= A1;
        }
        else
        {
            overflow = true;
        }
    }
    if (overflow)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << A << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

typedef pair<int,int> pii;
typedef long long int ll;
typedef long double ld;

const int DMAX = 1e5+10;

vector <int> vec;
vector <int> arb[DMAX];

bool V[DMAX];
bool uz[DMAX];

int n,q;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t,i,j;
    int x,y;

    cin>>n>>q;
    V[1]=true;
    uz[2]=true;
    for(i=1;i<=q;i++){
        cin>>x>>y;
        swap(uz[x],uz[y]);
        swap(V[x],V[y]);
        if(V[x])
            uz[x-1]=uz[x+1]=1;
        if(V[x-1] || V[x+1])
            uz[x]=1;
        if(V[y])
            uz[y-1]=uz[y+1]=1;
        if(V[y-1] || V[y+1])
            uz[y]=1;
    }
    int ans=0;
    for(i=1;i<=n;i++)
        ans+=(uz[i] || V[i]);
    cout<<ans<<'\n';

    return 0;
}


Measured memory_bytes: 2816
# coding: utf-8
import re
import bisect
from datetime import datetime as dt
import bisect
import math

def gcd(a, b):
    return math.gcd(a, b)

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

class slist(list):
    def __init__(self, *args, **kw):
        list.__init__(self, *args, **kw)
        self.sort()

    def append(self, value):
        bisect.insort(self,value)

    def index_left(self, value):
        return bisect.bisect_left(self, value)


if __name__ == '__main__':
    n, l = map(int, input().split())
    MIN = l
    MAX = l + n - 1
    ans = l * n + n * (n - 1) / 2
    if MIN >= 0:
        print(int(ans - l))
    elif MIN < 0 and 0 < MAX:
        print(int(ans))
    else:
        print(int(ans - MAX))


Measured memory_bytes: 3568
N = int(input())
S1 = input()
S2 = input()
mod = 1000000007
answer = 1
easy = []
i = 0

while N > i:
    if S1[i] == S2[i]:
        easy.append(1)
    else:
        easy.append(0)
        i += 1
    i += 1

for i in range(len(easy)):
    if i == 0:
        if easy[i] == 0:
            answer *= 6
        else:
            answer *= 3
    # elif i == 1:
    #     if easy[i] == 0:
    #         if easy[i-1] == 0:
    #             pass
    #         else:
    #             pass
    #     else:
    #         if easy[i-1] == 0:
    #             pass
    #         else:
    #             pass
    else:
        if easy[i] == 0:
            if easy[i-1] == 0:
                answer *= 3
            else:
                answer *= 2
        else:
            if easy[i-1] == 0:
                answer *= 1
            else:
                answer *= 2

print(answer % mod)


Measured memory_bytes: 3064
import numpy as np

A,B,C,X,Y = list(map(int,input().split()))
mnum = min([X,Y])
mval = min([A,B])
absep = A * X + B* Y 
minab = C * mnum  * 2 +  (X - mnum ) * A + (Y - mnum) * B 
allab = C  *  max([X,Y]) * 2

print(min([absep,minab,allab]))

Measured memory_bytes: 15256
/**
  @file a.cpp
  @title A - Tenki
  @url https://atcoder.jp/contests/abc139/tasks/abc139_a
**/

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

typedef long long LL;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, N) for (int i = 0; i < (N); ++i)

int main() {
  string S, T;
  cin >> S >> T;

  int ans = 0;
  REP(i, 3) {
    if (S.substr(i, 1) == T.substr(i, 1)) {
      ans++;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define db double
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define mem(x,val) memset(x,val,sizeof x)
#define Swap(a,b,n) for(int I=0;I<=n;I++) swap(a[I],b[I])
#define PC __builtin_popcountll
#ifdef DEBUG
	#define debug(A,args...) fprintf(stderr,A,##args)
#else
	#define debug(A,args...) printf("")
#endif
#define deb debug("line %d\n",__LINE__)
namespace mine
{
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
	template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
	ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
	bool IN(ll x,ll l,ll r){return l<=x and x<=r;}
	void GG(){puts("-1");exit(0);}

	const db eps=1e-8;
	const int INF=0x3f3f3f3f;
	const int MOD=1e9+7;
	int mm(const int x){return x>=MOD?x-MOD:x;}
	template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
	ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int MM=5e6+10;
	ll fac[MM],facinv[MM],Inv[MM];ll Comb(int n,int m){return n<0 or n<m?0:fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
	void PRE()
	{
		fac[0]=1;fo(i,1,MM-1) fac[i]=fac[i-1]*i%MOD;
		facinv[MM-1]=invm(fac[MM-1]);fd(i,MM-1,1) facinv[i-1]=facinv[i]*i%MOD;
		Inv[1]=1;fo(i,2,MM-1) Inv[i]=(MOD-MOD/i)*Inv[MOD%i]%MOD;
	}

	const int N=1e3+10;
	//------------------FIXED------------------
	int a[N][N];vc<pii> b;
	void main()
	{
		int n=qread();fo(i,1,n) fo(j,1,n) a[i][j]=qread(),b.PB({i,j});
		sort(all(b),[&](pii x,pii y){return a[x.FR][x.SE]<a[y.FR][y.SE];});
		ll ans=0;for(auto in:b)
		{
			int x=in.FR,y=in.SE;bool ok=0;
			fo(k,1,n) if(k!=x and k!=y) if(a[x][k]+a[k][y]<a[x][y]) GG();
			fo(k,1,n) if(k!=x and k!=y) if(a[x][k]+a[k][y]==a[x][y]) ok=1;
			if(!ok) ans+=a[x][y];
		}write(ans/2);
	}
};//变量重名！
signed main()
{
	#ifdef DEBUG
	//freopen("a.in","r",stdin);
	freopen("z.txt","r",stdin);
	//freopen("a.out","w",stdout);
	#endif
	srand(time(0));
	mine::main();
	debug("\n------------------------------------------\nTime: %.2lf s\n",1.0*clock()/CLOCKS_PER_SEC);
}

Measured memory_bytes: 2296
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    int a,b; cin >> a >> b;
    cout << a*b << endl;
}


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


int main()
{


     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
       long long int input;
    cin>>input;

    string nish="";
    while(input>0)
    {
      int rem=input%26;
      if(rem==0)rem=26;
      string temp(1,'a'+(rem-1));
      nish+=temp;
      input=(input-1)/26;
    }
    reverse(nish.begin(),nish.end());
    cout<<nish<<endl;
}

Measured memory_bytes: 3644
S = input()
if S == 'SSS':
  print(0)
elif S == 'SSR':
  print(1)
elif S == 'SRR':
  print(2)
elif S == 'SRS':
  print(1)
elif S == 'RSS':
  print(1)
elif S == 'RRS':
  print(2)
elif S == 'RRR':
  print(3)
elif S == 'RSR':
  print(1)


Measured memory_bytes: 8996
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
char s[100005];
int ans[100005];
int n,flag;
int check(int i,int x)
{
    int l = i - 1,r = i + 1;
    if(i == 1)l = n;
    if(i == n)r = 1;
    if(x)
    {
        if((s[i] == 'o' && ans[r] != ans[l]) || (s[i] == 'x' && ans[r] == ans[l]))
            return true;
        else return false;
    }
    else
    {
        if((s[i] == 'x' && ans[r] != ans[l]) || (s[i] == 'o' && ans[r] == ans[l]))
            return true;
        else return false;
    }
}
void dfs(int h,int x)
{
    if(flag)return;
    ans[h] = x;
    if(h > n)return;
    if(h == n && check(n,x) && check(1,ans[1]))
    {
        flag = 1;
        return ;
    }
    if(x)
    {
        if(s[h] == 'o')
        {
            dfs(h + 1,ans[h - 1]^1);
        }
        else
        {
            dfs(h + 1,ans[h - 1]);
        }
    }
    else
    {
        if(s[h] == 'o')
        {
            dfs(h + 1,ans[h - 1]);
        }
        else
        {
            dfs(h + 1,ans[h - 1]^1);
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        scanf("%s",s + 1);
        flag = 0;
        memset(ans,0,sizeof ans);
        ans[1] = 1;
        dfs(2,1);
        if(!flag)
        {
            memset(ans,0,sizeof ans);
            ans[1] = 1;
            dfs(2,0);
        }
        if(!flag)
        {
            memset(ans,0,sizeof ans);
            ans[1] = 0;
            dfs(2,0);
        }
        if(!flag)
        {
            memset(ans,0,sizeof ans);
            ans[1] = 0;
            dfs(2,1);
        }
        if(flag)
        {
            for (int i = 1; i <= n; i++)
            {
                if(ans[i])
                    printf("W");
                else printf("S");
            }
            printf("\n");
        }
        else printf("-1\n");
    }
}


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

int main(){
	int n,m;
	while(cin >> n >> m , n || m){
		int data[11] = {0};
		for(int i=0;i<n;i++){
			int a,b;
			cin >> a >> b;
			data[b] += a;
		}
		for(int i=10;i>=0;i--){
			if(data[i] <= m ){
				m -= data[i];
				data[i] = 0;
			}else{
				data[i] -= m;
				m = 0;
			}
		}
		int ans = 0;
		for(int i=0;i<=10;i++)
			ans += i * data[i];
		cout << ans << endl;
	}
}

Measured memory_bytes: 864
use std::str::FromStr;

fn get_one<T : FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().parse().ok().unwrap();
}

fn get_vec<T : FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
}

fn main() {
    let mut v : Vec<i32> = get_vec();
    v.sort();
    println!("{}", if v[0] + v[1] == v[2] { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
n = int(input())
a = []
b = []
c = []
for i in range(n):
    line = list(map(int, input().split()))
    a.append(line[0])
    b.append(line[1])
    c.append([line[0] + line[1], i])
c.sort(key = lambda x:x[0], reverse = True)
ans = 0
for i in range(n):
    if i%2 == 0:
        ans += a[c[i][1]]
    else:
        ans -= b[c[i][1]]
print(ans)


Measured memory_bytes: 77272
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		try (Scanner scan = new Scanner(System.in)) {
 
			int N = scan.nextInt();
			int W = scan.nextInt();
 
			int[] wArray = new int[N+1];
			int[] v = new int[N+1];
			
			for(int i=1; i<N+1; i++) {
				wArray[i] = scan.nextInt();
				v[i] = scan.nextInt();
			}
			
			long[][] dp = new long[N+1][W+1];
			
			for(int i=0; i<W+1; i++) dp[0][i] = 0;
			
			for(int w=1; w<W+1; w++) {
				for(int i=1; i<N+1; i++) {
					if(wArray[i] > w) {
                     	dp[i][w] = dp[i-1][w];
                    } else {
						dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-wArray[i]]+v[i]);
                    }
				}
			}
			
			System.out.println(dp[N][W]);
		}
	}
}

Measured memory_bytes: 125012
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;

ll oddsum(ll a){ return ( a + 1) / 2 % 2;}
ll solve(ll b){
  if(b % 2 == 1){  return oddsum(b);}
  else return oddsum( b + 1) ^ ( b + 1);}



int main(){ ll A,B ; cin >> A >> B;
 cout << (solve(B) ^ solve(A-1)) << endl; return 0;}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define for(i,a,b) for(int i=a;i<=b;i++)
#define _inline __inline__ __attribute__((always_inline))
using namespace std;
_inline void read(int &x){
	int res=0,f=1;
	char c=getchar();
	if(c=='-') f=-1;
	while(c>'9'||c<'0') c=getchar();
	while(c>='0'&&c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	x=res*f;
}
inline void print(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n;
string s;
int maxn=0;
int main(){
	read(n);
	int cnt=0;
	cin>>s;
	for(i,0,n-1){
		if(s[i]=='I') cnt++;
		else cnt--;
		maxn=max(maxn,cnt);
	}
	print(maxn),puts("");
	exit(0);
}

Measured memory_bytes: 256
# 数値の取得
polynum = int(input())
length = list(map(int,input().split()))

# 図形の成立可否を検証し結果を出力
most_l = max(length)
othersum = sum(length) - most_l
if othersum > most_l:
    print("Yes")
else:
    print("No")

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

int solve(int a){
  int sum = 0;

  for(int i=1;i<a;i++){
    for(int j=1;j<=10;j++){
      if(i % 3 == 0) sum += 20;
      else if(j % 2 == 0) sum += 19;
      else if(j % 2 == 1) sum += 20;
    }
  }

  return sum;
}

int main(){

  int n;
  int y,m,d;
  long long int sum = 0;
  long long int ans = 0;

  ans = (solve(1000)+1);

  cin >> n;
  for(int l=0;l<n;l++){
    cin >> y >> m >> d;

    sum = (solve(y)+d);

    for(int i=1;i<m;i++){
      if(y % 3 == 0) sum += 20;
      else if(i % 2 == 0) sum += 19;
      else if(i % 2 == 1) sum += 20;
    }

    cout << ans - sum << endl;

  }

}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n;
    cin>>n;
    ll a;
    rep(i,n){
        cin>>a;
        if(a%2==0){
            if(a%3!=0&&a%5!=0){
                cout<<"DENIED"<<endl;
                return 0;
            }
        }
    }
    cout<<"APPROVED"<<endl;
    return 0;
}

Measured memory_bytes: 256
INF = 10**18
n, w = map(int, input().split())

weights = [0]
values = [0]

for i in range(n):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

max_value = sum(values)
dp = [[INF for i in range(max_value+1)] for j in range(n+1)]

for i in range(n+1):
    dp[i][0] = 0

for i in range(n+1):
    for j in range(max_value + 1):

        if values[i] <= j:
            dp[i][j] = min(dp[i-1][j], weights[i] + dp[i-1][j - values[i] ] )
        else:
            dp[i][j] = dp[i-1][j]

ans = 0

for i in range(max_value + 1):
    if dp[n][i] <= w:
        ans = i

print(ans)
#print(dp)

Measured memory_bytes: 171244
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  ll n,k;
  cin>>n>>k;
  // if(k>n)
  // {
  //   cout<<1<<endl;
  //   return 0;
  // }
  ll sum=1;
  n++;
  for (ll i = k; i < n; ++i)
  {
    sum+=i*(2*n-i+1)/2-i*(i+1)/2+1;
    sum%=mod;
  }
  cout<<sum%mod<<endl;
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastReader s = new FastReader();
        int T = s.nextInt();
        if(T%1000==0)
            System.out.println(0);
        else
            System.out.println(1000-T%1000);
    }

    private static boolean isPrime(int n) {
        if (n == 2)
            return true;
        else if ((n % 2 == 0 && n > 2) || n < 2)
            return false;
        else {
            for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }


    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

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

int main() {
    int N,ans=0;
    string S;
    cin >> N >> S;
    for (int i = 0; i < N-2; i++) {
        if (S.substr(i,3) == "ABC") {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    int n, a;
    cin >> n;
    for (int i = n; i >= 1; i--){
        if (n == 1){
            a = 1;
            break;
        }if (pow(2, i) <= n){
            a = pow(2, i);
            break;
        }
    }
    cout << a;

    return 0;
}


Measured memory_bytes: 256
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def inpm(line):
    return [inp() for _ in range(line)]


def inpfm(line):
    return [inpf() for _ in range(line)]


def inpsm(line):
    return [inps() for _ in range(line)]


def inlm(line):
    return [inl() for _ in range(line)]


def inlfm(line):
    return [inlf() for _ in range(line)]


def inlsm(line):
    return [inls() for _ in range(line)]


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


a = inl()
a.sort()
print(a[0] + a[1])


Measured memory_bytes: 3572
#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int MAX=210000;
const int MOD=1e9+7;

typedef long long ll;

ll fac[MAX],finv[MAX],inv[MAX];

ll mod_pow(ll x, ll n){ //べき乗
    ll ans=1;
    while(n!=0){
        if(n&1) ans=ans*x%MOD;
        x=x*x%MOD;
        n=n>>1;
    }
    return ans;
}

void com_init(){ //初期化
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        //inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        //finv[i]=finv[i-1]*inv[i]%MOD;
        finv[i]=finv[i-1]*mod_pow(i,MOD-2)%MOD;//フェルマーの小定理より
    }
}

ll comb(ll n, ll k){ //nCk
    if(n<k) return 0;
    if(n<0||k<0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

int main(){
    com_init();
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<bool> used(100010,false);
    map<int,int> res;
    for(int i=0;i<=n;i++){
        cin >> a[i];
    }
    int first=0,second=0;
    for(int i=0;i<=n;i++){
        if(used[a[i]]==true){
            second=i;
            break;
        }else{
            used[a[i]]=true;
        }
    }
    for(int i=0;i<=n;i++){
        if(a[i]==a[second]){
            first=i;
            break;
        }
    }
    for(int i=1;i<=n+1;i++){
        ll ans=(comb(n+1,i)-comb(first+n-second,i-1)+MOD)%MOD;
        cout << ans << endl;
    }
}

Measured memory_bytes: 4864
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N; cin>>N;
    ll A=0,B=0,BA=0,ans=0;
    rep(i,N){
        string tmp; cin>>tmp;
        if(tmp[0]=='B' && tmp[sz(tmp)-1]=='A') BA++;
        else if(tmp[0]=='B') B++;
        else if(tmp[sz(tmp)-1]=='A') A++;
        
        rep(j,sz(tmp)-1){
            if(tmp[j]=='A' && tmp[j+1]=='B') ans++;
        }
    }
    
    ll B_use=min(1ll,B);
    ll A_use=min(1ll,A);
    ans += max((B_use+BA+A_use)-1,0ll);
    ans+=min(B-B_use,A-A_use);
    cout<<ans<<endl;
}



Measured memory_bytes: 3580
package main

import(
  "fmt"
  "math"
)

func main() {
  var a, b int
  fmt.Scan(&a, &b)
  search := func() int {
    for i := 1; i <= 1000; i++ {
      a_can:=math.Trunc(float64(i)*0.08)
      b_can:=math.Trunc(float64(i)*0.1)
      if int(a_can)==a && int(b_can)==b {
        return i
      }
    }
    return -1
  }()
  fmt.Print(search)


}


Measured memory_bytes: 512