akhauriyash/Code-Regression huggingface dataset:
// ~maqsat~
/*
```````````````````````¶¶
````````````````````¶¶¶¶¶¶¶¶
```````````````````¶¶¶¶¶¶¶¶¶¶
```````````````````¶¶¶¶¶¶``¶¶¶
``````````````````¶````¶````¶¶
``````````````````¶```¶¶¶```¶¶¶
`````````````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
````````````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶```````````¶¶
```````````````¶¶¶¶¶````¶¶¶¶¶`¶¶¶¶¶``````¶¶¶¶¶¶¶¶¶
`````````````¶¶¶¶¶````````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶`
`````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶```¶¶¶
```¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
`¶¶``¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
``````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
```````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
```````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
`````````¶¶``````¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
```````````````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶
```````````````````¶¶¶¶¶¶¶¶¶¶¶¶¶¶
````````````````````¶¶¶¶¶¶¶¶¶¶¶¶
`````````````````````¶¶¶¶¶¶¶¶¶¶¶
``````````````````````¶¶¶¶¶¶¶¶¶
````````````````````````¶¶¶¶¶
                 ready for halloween
*/
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("Ofast")
// #pragma GCC optimization ("unroll-loops")
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define F first
#define S second
#define in insert
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define count1 __builtin_popcountl
#define debug(x) cerr << (#x) << " = " << (x) << "\n"
#define ACCELERATE ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define fre(f) if(fopen(f".in", "r")) freopen(f".in", "r", stdin),freopen(f".out", "w", stdout)
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
using db = double;
using ld = long double;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
 
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> inline void cmin(T &a, T b) { a = min(a, b); }
template <class T> inline void cmax(T &a, T b) { a = max(a, b); }
 
const int oo = 0x3f3f3f3f;
const ll N = 2e5 + 345;
const ll MOD = 1e9 + 7;
const ll INF = 1e10 + 9;
const db EPS = 1e-9;
const db PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

int main() {
    fre("");
    ACCELERATE;
    
    #define int ll
    
    int n;
    cin >> n;
    
    int a[N];
    for(int i = 0; i < n; i++) cin >> a[i];
    
    int dp[N];
    dp[0] = 0;
    dp[1] = abs(a[0] - a[1]) + dp[0];
    for(int i = 2; i < n; i++) {
    	if(dp[i-1] + abs(a[i] - a[i-1]) > dp[i-2] + abs(a[i] - a[i-2])) {
    		dp[i] = dp[i-2] + abs(a[i] - a[i-2]);
    	}
    	else {
    		dp[i] = dp[i-1] + abs(a[i] - a[i-1]);
    	}
    }
    
    cout << dp[n-1];
    return 0;
}
/*
 
*/

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

vector<vector<int>> divisors_table(int n) {
    vector<vector<int>> divisors(n + 1);
    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) divisors[j].emplace_back(i);;
    }
    return divisors;
}

int main() {
    int n; cin >> n;
    auto divisors = divisors_table(n);
    int cnt = 0;
    for (int i = 1; i <= n; i += 2) cnt += divisors[i].size() + 1 == 8;
    cout << cnt << endl;
    return 0;
}


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

int main(){
    double n,k;
    cin >> n >> k;
    double ans=0;
    for(double i=1;i<=n;i++){
        double p = 1.0/n;
        double tmp = i;
        while(tmp < k){
            p/=2;
            tmp *= 2;
        }
        ans += p;
    }
    printf("%.12f\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int bulb[10], p[10];

int countbits(int i) {
	int c;
	for (c = 0; i; c++) i &= i-1;
	return c;
}

int main(void) {
	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++) {
		int k;
		scanf("%d", &k);
		bulb[i] = 0;
		for (int j = 0; j < k; j++) {
			int c;
			scanf("%d", &c);
			bulb[i] |= 1<<(c-1);
		}
	}
	for (int i = 0; i < m; i++) scanf("%d", &p[i]);

	int cnt = 0;
	for (int i = 0; i < 1<<n; i++) {
		int ok = 1;
		for (int j = 0; ok && j < m; j++)
			ok = countbits(bulb[j]&i)%2 == p[j];
		cnt += ok;
	}
	printf("%d\n", cnt);
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
int main()
{
	long n,a[114514],b[114514],c=0;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	for(int i=n-1;~i;i--)
	{
		a[i]+=c;
		c+=(b[i]-a[i]%b[i])%b[i];
	}
	cout<<c<<endl;
}

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  ll x;cin>>x;
  ll m = 100;
  rep(i, 10000){
    m *= 1.01;
    if((ll)m>=x) { cout<<i+1<<endl; return 0;}
  }
  return 0;
}

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

typedef long long LL;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
int a[MAXN], b[MAXN - 1];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; ++i)
		cin >> b[i];
	LL ans = 0;
	a[0] = b[0];
	for (int i = 1; i < n - 1; ++i)
		a[i] = min(b[i - 1], b[i]);
	a[n - 1] = max(b[n - 2], b[n - 1]);
	for (int i = 0; i < n; ++i)
		ans += a[i];
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

int dy[5] = { 0,0,1,-1,0 };
int dx[5] = { 1,-1,0,0 ,0 };


int main(void) {
	int a, b, k;
	bool flag = false;

	cin >> a >> b >> k;

	FOR(i, 1, k) {
		if (flag) {
			flag = false;
			if (b % 2 == 1) {
				b--;
			}
			a += (b / 2);
			b /= 2;
		}
		else {
			flag = true;
			if (a % 2 == 1) {
				a--;
			}
			b += (a / 2);
			a /= 2;
		}
	}

	cout << a << " " << b << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int num = scan.nextInt();
    int a = 0;
    
    for(int i=1;i<=9;i++){
      for(int j=1;j<=9;j++){
        if(i*j==num){
          a =1;
          break;
        }
      }
    }
    
    if(a==0){
    	System.out.println("No");
    }
    else{
      System.out.println("Yes");
    }
    
  }
}


Measured memory_bytes: 22868
n,m=map(int,input().split())
S=[list(map(int,input().split()))[1:] for _ in range(m)]
P=list(map(int,input().split()))

cnt=0
for i in range(2**n):
    Q=0
    switch=set([i+1 for i,j in enumerate(format(i,"b").zfill(n)[::-1]) if j == '1'])
    for k,j in enumerate(S):
        if len(switch&set(j))%2==P[k]:
            Q+=1
    if Q==m:
        cnt+=1

print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi= vector<vi>;
using vs = vector<string>;
using pl = pair<ll,ll>;
#define ci(n,a)   ll a[n]; rep(i,(n)) cin>>a[i];
#define rep(i,n)  for(ll i = 0; i < (n); ++i)
#define red(i,n)  for(ll i = (n)-1; i >= 0; --i)
#define all(a)    begin(a),end(a)
#define pb(a)     push_back(a)
#define mp(a,b)   make_pair(a,b)
#define yn(a)     cout << ( (a)?"Yes\n":"No\n" )
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll INF = 1e9+9, LINF = 1e18;


int main(int argc,char* argv[]) 
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;

    cout<<(a-c)*(b-d)<<endl;
    return 0;
}


Measured memory_bytes: 256
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List
import Text.Printf

main :: IO ()
main = do
  [h,m,s] <- getl $ split toInt
  unless (h == (-1) && m == (-1) && s == (-1)) $ do
    mapM_ printTime $ solve (h,m,s)
    main

solve :: (Int,Int,Int) -> [(Int,Int,Int)]
solve x = [toTime t, toTime (3 * t)]
  where
    t = 7200 - fromTime x

printTime :: (Int,Int,Int) -> IO ()
printTime (h,m,s) = printf "%02d:%02d:%02d\n" h m s

fromTime :: (Int,Int,Int) -> Int
fromTime (h,m,s) = h * 3600 + m * 60 + s

toTime :: Int -> (Int,Int,Int)
toTime s = (s `div` 3600, s `mod` 3600 `div` 60, s `mod` 60)

toInt :: String -> Int
toInt s = read s

split :: (String -> a) -> String -> [a]
split f = map f . words

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 4144
# cook your dish here
n=int(input())
a=[int(x) for x in input().split()]
ans=1  
mod=int(1e18)
for i in range(n):
    if a[i]==0:
        ans=0 
        break 
for i in range(n):
    ans*=a[i]
    if ans>mod:
        ans=-1 
        break 
    if ans==0:
        break
print(ans)

Measured memory_bytes: 21620
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
typedef long long ll;
using namespace std;
vector<int> V;

vector<ll> fct(1000010, 1);
vector<ll> invfct(1000010, 1);

ll comb(ll a, ll b){
    if(a==0 && b==0) return 1;
    if(a<b || a < 0) return 0;
    ll tmp = invfct[a-b] * invfct[b] % 1000000007;
    return tmp * fct[a] % 1000000007;
}



ll solve(int i, int j){
    ll count = 0;
    while(true){
        if(2 * j == i) break;
        i -= 1;
        j -= 2;
        count += 1;
    }
    ll hoge = count + i / 2;
    return comb(hoge, count);
}

ll mod_pow(ll n, ll p) {
    if(p==0) return 1;
    ll res = mod_pow(n*n % 1000000007, p / 2);
    if(p%2==1) res = res * n % 1000000007;
    return res;
}

int main(void){
    // Your code here!
   int X, Y;
   cin >> X >> Y;
   
   if(Y > 2 * X || 2 * Y < X) {
       cout << 0 << endl;
       return 0;
   }
   
   if(Y == 2 * X || 2 * Y == X) {
       cout << 1 << endl;
       return 0;
   }
   
   fct[0] = 1;
   invfct[0] = 1;
   for(ll i = 0; i < 1000010; i++){
       fct[i+1] = (fct[i] * (i+1)) %1000000007;
       invfct[i+1] = (invfct[i] * mod_pow(i+1, 1000000007-2)) % 1000000007;
   }
   
   if( (2 * X - Y) % 3 != 0 ) cout << 0 << endl;
   else cout << solve(X, Y) << endl;
   return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 2e5 + 50;
const int mod = 1e9 + 7;
const int inf = 1e17;
int dx[] = {0, 1, -1, 0, -1, 1, 1, -1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int sum[N];
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); 
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  for(int i = 1; i < n; i++){
  	if(s[i] == 'C' && s[i - 1] == 'A'){
  		sum[i + 1] = sum[i] + 1;
  	}else{
  		sum[i + 1] = sum[i];
  	}
  }
  while(q--){
  	int l, r;
  	cin >> l >> r;
  	int ans = sum[r] - sum[l - 1];
  	l--;
  	if(l){
  		if(s[l] == 'C' && s[l - 1] == 'A'){
  			ans--;
  		}
  	}
  	cout << ans << endl;
  }
}

Measured memory_bytes: 1872
#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;

int dfs(vector<int> l,int cur,int a,int b, int c){
	if(cur == n)
	{
		if(min({a,b,c}) > 0)
		{
			return abs(a-A)+abs(b-B)+abs(c-C)-30;
		}
		else
		{
			return pow(10,9);
		}
	}
	int ret0 = dfs(l,cur+1,a,b,c);
	int ret1 = dfs(l,cur+1,a+l.at(cur),b,c)+10;
	int ret2 = dfs(l,cur+1,a,b+l.at(cur),c)+10;
	int ret3 = dfs(l,cur+1,a,b,c+l.at(cur))+10;
	return min({ret0,ret1,ret2,ret3});
}

int main() {
	cin >> n >> A >> B >> C;
	vector<int> l(n);
	for(int i=0;i<n;i++)
	{
		cin >> l.at(i);
	}
	cout << dfs(l,0,0,0,0) << endl;
	return 0;
}


Measured memory_bytes: 3564
n, m = list(map(int, input().split()))

a = [list(map(int, input().split())) for _ in range(m)]

ans = [0 for _ in range(n)]
check = [False for _ in range(n)]

flag = 0

for i, j in a:
    if check[i-1] == 0 or ans[i-1] == j:
        ans[i-1] = j
        check[i-1] = True
    else:
        flag = 1
       
if check[0] == False and ans[0] == 0 and m != 0:
    ans[0] = 1
elif m == 0 and n != 1:
    ans[3-n] = 1

c = ""
for k in ans:
    c += str(k)

if flag == 1 or len(str(int(c))) != n:
    print(-1)
else:
    print(c)


Measured memory_bytes: 3064
#include <cstdio>
#define IL inline
#define N 2003
#define REP(a,b,c) for(a=b;a<=c;a++)
using namespace std;
typedef long long lol;
const int mod=1e9+7;
IL int qpow(int a,int b){
	int res=1;while(b){if(b&1)res=1LL*res*a%mod;a=1LL*a*a%mod,b>>=1;}return res;
}
int n,k,fac[N*N],inv[N*N],f[N][N];
IL lol C(int n,int m){
	return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
IL void work(){
	int i,j=n*k,t;fac[0]=1;
	REP(i,1,j)fac[i]=1LL*fac[i-1]*i%mod;inv[j]=qpow(fac[j],mod-2);
	for(i=j;i;i--)inv[i-1]=1LL*inv[i]*i%mod;
	f[0][0]=1;k--;
	REP(i,0,n)REP(j,i,n){
		t=f[i][j];if(i<j)f[i+1][j]=(f[i+1][j]+t)%mod;
		f[i][j+1]=(f[i][j+1]+t*C(i-1+k*(j+1),k-1))%mod;
	}
	printf("%lld\n",1LL*f[n][n]*fac[n]%mod);
}
int main(){
  scanf("%d%d",&n,&k);
	if(k==1)printf("1");else work();
  return 0;
}

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


fn divisor(n : u64) -> Vec<u64> {
    let mut x = n;
    let mut v = Vec::new();
    let mut i : u64= 2;
    while i.pow(2) <= n {
        while x % i == 0 {
            v.push(i);
            x = x / i;
        }
        i+=1;
    }
    if x != 1 {
        v.push(x);
    }
    return v;
}

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 n : u64 = get_one();
    let mut v : Vec<u64> = vec!(0;(n+1) as usize);
    for i in 2..(n+1) {
        let w = divisor(i);
        for x in w {
            v[x as usize] += 1;
        }
    }
    let ans = v.iter().fold(1, |pr, x| (pr * (x+1)) % 1000000007);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

Measured memory_bytes: 256
from collections import Counter

def solve(s):
    cs = Counter(s).most_common()
    m = len(s)
    for c in cs:
        news = list(s)
        size = len(s)
        count = 0
        while len(Counter(news[:size]).most_common()) > 1:
            for i in range(size - 1):
                if news[i] != c[0] and news[i + 1] == c[0]:
                    news[i] = c[0]
            size -= 1
            count += 1
        if count < m:
            m = count
    return m

_s = input()
print(solve(_s))


Measured memory_bytes: 43112
<?php
fscanf(STDIN,"%d %d",$n,$x);
$l_arr=explode(' ',trim(fgets(STDIN)));


$d_arr=array();
$d_arr[0]=0;
for($i=1;$i<=$n;$i++){
	$d_arr[$i-1]=$d_arr[$i-2]+$l_arr[$i-1];
}
$d_arr[$n+1]=0;
sort($d_arr);
$cnt=0;
for($i=0;$i<=$n;$i++){
	if($d_arr[$i]<=$x){
		$cnt++;
	}
}
//print_r($d_arr);
echo $cnt;

?>

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

int main () {
    int a, b, c, k;

    cin >> a >> b >> c >> k;

    int u = 0;
    while (b <= a) {
        b *= 2;
        ++ u;
    }

    while (c <= b) {
        c *= 2;
        ++ u;
    }

    printf(u <= k ? "Yes" : "No");
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 3684
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int x[1000005];
int n;
int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> x[i];
	}
	int cur = 2; ll ret = 1LL*(x[0]-1);
	for(int i=1;i<n;i++){
		if(x[i] == cur){
			cur++; continue;
		}
		ll a = x[i]/cur;
		ret += a; x[i] -= a*cur; if(x[i]==0){ ret--; }
	}
	cout << ret << endl;
}

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int k[m];

    int s[10][10] = {0};
    for (int i = 0; i < m; ++i){
        cin >> k[i];
        for(int j = 0; j < k[i]; ++j){
            cin >> s[i][j];
        }
    }

    int p[m];
    for (int i = 0; i < m; ++i) cin >> p[i];

    int res = 0;
    for (int i = 0; i < 1<<n; ++i){
        int on[n] = {0};

        for (int j = 0; j < n; ++j){

            if(i & (1<<j)){
                on[j] = 1;
            }
        }

        bool flg = true;

        for (int j = 0; j < m; ++j){
            int cnt = 0;
            for(int l = 0; l < k[j]; ++l){
                cnt += on[s[j][l] - 1];
            }
            
            if(cnt%2 != p[j]) flg = false;
        }

        if(flg) res++;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

constexpr int INF = 2000000000;

int main() {
  auto min = [](int a, int b) { return a < b ? a : b; };
  int K, N;
  std::cin >> K >> N;
  std::vector<int> A(2 * N);
  for (int i = 0; i < N; i++) {
    std::cin >> A[i];
    A[i + N] = A[i] + K;
  }

  int res{INF};
  for (int i = 0; i < N; i++) res = min(res, A[i + N - 1] - A[i]);

  std::cout << res << std::endl;
}

Measured memory_bytes: 1792
# 基本的に問題はここで解く。

input = gets.chomp.split("")

c_count = 0

(input.length).times do |i|
    
    if i == 0
        if input[i] == "A" 
            next
        else
            puts "WA"
            exit
        end
    end

    if input[i] == "C" && i >= 2 && i <= (input.length - 2)
        c_count += 1
        if c_count == 2
            puts "WA"
            exit
        end
    # Cではない大文字ならWA
    elsif input[i].match(/\p{Upper}/)
        puts "WA"
        exit
    end

end

if c_count == 0
    puts "WA"
    exit
end

puts "AC"



Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int r, g, b, n;
    cin >> r >> g >> b >> n;
    int ans = 0;
    rep(i, n / r + 1)
    {
        rep(j, n / g + 1)
        {
            int tmp = n - i * r - j * g;
            if (tmp % b == 0 && 0 <= tmp / b)
                ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n, m, l = map(int, input().split())
A = []
for i in range(0, n):
    A.append(list(map(int, input().split())))

B = []
for i in range(0, m):
    B.append(list(map(int, input().split())))

C = []
for i in range(0, n):
    row = []
    for j in range(0, l):
        sum = 0
        for k in range(0, m):
            sum += A[i][k] * B[k][j]
        row.append(sum)
    C.append(row)

for i in range(0, n):
    print(" ".join(map(str, C[i])))



Measured memory_bytes: 6904
use std::io;
use std::io::prelude::*;
use std::io::{BufWriter,Write};

// 左子右兄弟表現を用いる
struct Node {
    id: u32,
    parent: Option<usize>,
    child: Option<usize>,   // 1つ目の子供
    sib: Option<usize>, // 下の兄弟
    depth: u32, 
}

impl Node {
    fn new(id: u32) -> Node {
        Node {
            id: id,
            parent: None,
            child: None,
            sib: None,
            depth: 0,
        }
    }

    fn _rec_calc_depth(nodes: &mut Vec<Node>, cur_depth: u32, cur_id: usize){
        nodes[cur_id].depth = cur_depth;
        if let Some(ch) = nodes[cur_id].child {
            Node::_rec_calc_depth(nodes, cur_depth+1, ch);
        }
        
        if let Some(sib) = nodes[cur_id].sib {
            Node::_rec_calc_depth(nodes, cur_depth, sib);
        }
    }

    fn calc_depth(nodes: &mut Vec<Node>) {
        for i in 0..nodes.len() {
            if nodes[i].parent.is_none() {
                Node::_rec_calc_depth(nodes, 0, i);
                break;
            }
        }
    }

    fn print(nodes: &Vec<Node>) {
        let out = io::stdout();
        let mut out = BufWriter::new(out.lock());

        for node in nodes {
            write!(out, "node {}: ", node.id).unwrap();
            write!(out, "parent = {}, ", match node.parent {
                Some(x) => x.to_string(),
                None => String::from("-1"),
            }).unwrap();
            write!(out, "depth = {}, ", node.depth).unwrap();
            if node.parent.is_none() {
                write!(out, "root, ").unwrap();
            } else if node.child.is_none() {
                write!(out, "leaf, ").unwrap();
            } else {
                write!(out, "internal node, ").unwrap();
            }

            write!(out, "[").unwrap();
            if let Some(c) = node.child {
                write!(out, "{}", c).unwrap();
                let mut sib = nodes[c].sib;
                while let Some(s) = sib {
                    write!(out, ", {}", s).unwrap();
                    sib = nodes[s].sib;
                }
            }
            write!(out, "]\n").unwrap();
        }
    }
}

fn main() {
    let sin = io::stdin();
    let mut l_iter = sin.lock().lines();
    let n: usize = l_iter.next().unwrap().unwrap().trim().parse().unwrap();

    let mut nodes = (0..n)
        .map(|v| Node::new(v as u32))
        .collect::<Vec<Node>>();

    for line in l_iter {
        let l = line.unwrap();
        let vals = l.split_whitespace()
            .map(|v| v.parse::<usize>().unwrap())
            .collect::<Vec<usize>>();
        let idx = vals[0];
        if vals[1] > 0 {    // 子供の数を比較
            let childs = &vals[2..];
            nodes[idx].child = Some(childs[0]);   // 1番目の子供

            // i番目以降の子供をi-1番目の兄弟として登録
            for i in 0..vals[1] {
                nodes[childs[i]].parent = Some(idx);
                if i < vals[1] - 1 {
                    nodes[childs[i]].sib = Some(childs[i+1]);
                }
            }
        }
    }
    Node::calc_depth(&mut nodes);
    Node::print(&nodes);
}



Measured memory_bytes: 15160
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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

    string s;
    cin>>s;
    if (s[2] == s[3] && s[4] == s[5]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 != 0 && i % 5 != 0) {
                sum += i;
            }
        }

        System.out.println(sum);
    }
}

Measured memory_bytes: 27192
#include<bits/stdc++.h>
#include<deque>
using namespace std;
int main() {

    int q,f,d,x,p;
    deque<int>Q;
    cin>>q;
    while(q--) {
        cin>>f;

        if(f==0) {
            cin>>d>>x;
            if(d==0)
                Q.push_front(x);
            if(d==1)
                Q.push_back(x);
        }

        else if(f==2) {
            cin>>d;

            if(d==0)
                Q.pop_front();

            if(d==1)
                Q.pop_back();
        } else if(f==1) {
            cin>>p;

            cout<<Q[p]<<endl;
        }
    }

    return 0;
}




Measured memory_bytes: 4668
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f

using namespace std;

struct Edge {
  int t,next;
  Edge() {}
  Edge(int a,int b):t(a),next(b) {}
};

Edge e[200005];
int head[100005];

int f[100005][2];

void dfs(int x,int fa) {
  f[x][1]=-inf;
  for(int i=head[x];i;i=e[i].next)
    if (e[i].t!=fa) {
    	int u=e[i].t;
    	dfs(u,x);
    	f[x][0]+=max(f[u][0],f[u][1]);
    	f[x][1]=max(f[x][1],f[u][0]+2-max(f[u][0],f[u][1]));
	}
  f[x][1]+=f[x][0];
}

int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<n;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[2*i-1]=Edge(y,head[x]);
  	head[x]=2*i-1;
  	e[2*i]=Edge(x,head[y]);
  	head[y]=2*i;
  }
  dfs(1,0);
  puts((max(f[1][0],f[1][1])==n)?"Second":"First");
  return 0;
}

Measured memory_bytes: 2944
#include <iostream>

using namespace std;

int dp[1001]{};

int main() {
	int d,g;
	cin >> d >> g;
	g/=100;
	for(int i = 0; i < d; i++) {
		int p,c;
		cin >> p >> c;
		c/=100;
		for(int k = 1000; k > 0; k--) {
			int _m = 0;
			for(int j = 1; k-j>=0 && j<=p; j++) {
				int _sc = dp[k-j]+(i+1)*j;
				if(j==p) _sc += c;
				_m = max(_m,_sc);
			}
			dp[k] = max(dp[k],_m);
		}
	}
	for(int i = 0; i <= 1000; i++) {
		if(dp[i]>=g) {
			cout << i << endl;
			return 0;
		}
	}
}


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

// Template START
#define endl "\n"
#define async ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long int
#define all(y) y.begin(), y.end()
#define present( x, y ) (x.find( y ) != x.end())
const int mod = (int)1e9 + 7 ;
#define vv(T) vector<vector<T>>
#define vvv(T) vector<vector<vector<T>>>
template<class T>
auto matrix( int r, int c, T v ){
    return vector<vector<T>>( r, vector<T>( c, v ) ) ;
}
template<class T>
auto matrix( int o1, int o2, int o3, T v ){ 
    return vector<vector<vector<T>>>( o1, vector<vector<T>>( o2, vector<T>( o3, v ) ) ) ;
}
// Template END

int power( int x, int n ){
    if( n == 0 ) return 1 ;
    else if( n & 1 ) return ( x * power( (x*x) % mod, n / 2 ) ) % mod ;
    return power( (x*x) % mod, n / 2 ) % mod ;
}
void absorb( int &product, int &x ){
    product = ( product * (x % mod) ) % mod ;
    if( product < 0 ) product += mod ;
}


signed main(){
    int n, k ; cin >> n >> k ;
    vector<int> a(n) ;
    for( int i = 0 ; i < n ; i++ ){
        cin >> a[i] ;
    }
    sort( all(a) ) ; int ans = 1 ;
    if( a[n-1] <= 0 && (k & 1) ) {
        reverse( all(a) ) ;
        for( int i = 0 ; i < k ; i++ ){
            absorb( ans, a[i] ) ;
        }
        cout << ans ;
        return 0 ;
    }
    n-- ;
    // cout << k << " " << n << endl ;
    if( k & 1 ){
        absorb( ans, a[n] ) ;
        k-- ;
        n-- ;
    }
    int i = 0 ;
    while( k > 0 ){
        int f = a[i] * a[i+1], s = a[n] * a[n-1] ;
        if( f > s ){
            f %= mod ;
            absorb( ans, f ) ;
            i += 2 ;
        }
        else{
            s %= mod ;
            absorb( ans, s ) ;
            n -= 2 ;
        }
        k -= 2 ;
    }
    cout << ans ;
    return 0 ;   
}


Measured memory_bytes: 4804
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int a[100005],n,b[100005],c[100005],bit[200005];
ll sum,res;
void add(int x){for(;x<=200002;x+=x&-x)bit[x]++;}
int qur(int x){int tmp=0;for(;x;x-=x&-x)tmp+=bit[x];return tmp;}
bool check(int k){
	res=0,sum=100002;memset(bit,0,sizeof bit);
	for(int i=1;i<=n;++i)if(a[i]<=k)b[i]=1;else b[i]=-1;
	add(sum);
	for(int i=1;i<=n;++i){
		sum+=b[i];
		res+=qur(sum-1);
		add(sum);
	}
	return res>=(1ll*n*(n+1)>>2)+1;
}
int main(){
	n=read();for(int i=1;i<=n;++i)a[i]=c[i]=read();
	sort(c+1,c+n+1);
	int l=1,r=n,mid;
	while(l<r){
		mid=l+r>>1;
		if(check(c[mid]))r=mid;
		else l=mid+1;
	}
	printf("%d",c[r]);
}

Measured memory_bytes: 2176
// E - Knapsack2 https://atcoder.jp/contests/dp/tasks/dp_e
/* 入力例
3 8
3 30
4 50
5 60
// →出力　90
*/
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    int N, W;
    int INF = INT_MAX / 2;
    cin >> N >> W;
    long long int v[N], w[N], dp[N][N * 1000 + 1];
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= N * 1000 + 1; j++) {
            if(i == 0) {
                if(j <= v[i])
                    dp[i][j] = w[i];
                else
                    dp[i][j] = INF;
            } else {
                if(j <= v[i])
                    dp[i][j] = min(dp[i - 1][j], w[i]);
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    int flag = 0;
    for(int j = 0; j < N * 1000 + 1; j++) {
        if(dp[N - 1][j] <= W && dp[N - 1][j + 1] > W) {
            cout << j << endl;
            flag = 1;
        }
    }
    if(flag == 0) cout << N * 1000 << endl;
    return 0;
}


Measured memory_bytes: 78336
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int MAXN = 100000 + 1000;
const int MAXM = 3000 + 10;

bool isp[MAXM];
int pri[MAXM], totp = 0;

void init()
{
	memset(isp, true, sizeof(isp));
	isp[0] = isp[1] = false;
	for(int i = 2; i < MAXM; i++)
	{
		if(isp[i])
			pri[++totp] = i;
		for(int j = 1; j <= totp && i * pri[j] < MAXM; j++)
		{
			isp[i * pri[j]] = false;
			if(i % pri[j] == 0)
				break;
		}
	}
}

bool is_square(long long x)
{
	int y = sqrt(x) + 0.5;
	return (long long)y * y == x;
}

int n;
long long a[MAXN];
set<long long> S;
map<long long, int> cnt1, cnt2;

void work()
{
	for(int i = 1; i <= n; i++)
	{
		long long val1 = 1, val2 = 1;
		long long tmp = a[i];
		for(int j = 1; j <= totp; j++)
			if(tmp % pri[j] == 0)
			{
				int cnt = 0;
				while(tmp % pri[j] == 0)
					tmp /= pri[j], cnt++;
				cnt %= 3;
				if(cnt == 1)
					val1 *= pri[j], val2 *= pri[j] * pri[j];
				else if(cnt == 2)
					val2 *= pri[j], val1 *= pri[j] * pri[j];
			}
		val1 *= tmp;
		if(is_square(tmp))
			val2 *= (int)(sqrt(tmp) + 0.5);
		else if((double)val2 * tmp * tmp < 1e18)
			val2 *= tmp * tmp;
		else
			val2 = 0;
		S.insert(val1), cnt1[val1]++, cnt2[val2]++;
	}
	int ans = n, rem = 0;
	if(S.count(1))
		ans -= cnt1[1], ans += 1, S.erase(1);
	for(set<long long>::iterator it = S.begin(); it != S.end(); it++)
	{
		long long val = *it;
		// cerr << val << ' ' << cnt1[val] << ' ' << cnt2[val] << endl;
		rem += min(cnt1[val], cnt2[val]);
	}
	ans = ans - rem / 2;
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	init();

	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	work();


	return 0;
}


Measured memory_bytes: 20696
import sys
input = sys.stdin.readline
n,m=map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(1,m+1):
    tmp = 0
    for j in range(n):
        if i in lst[j][1:]:
            tmp += 1
    if tmp == n:
        cnt +=1
print(cnt)


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cmath>
typedef long long ll;
using namespace std;
ll n;
ll a[100010];
ll dis[100010];
int main()
{
    ll sum=0;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    ll k;
    if((2*sum%(n*(n+1)))!=0)
    {
        printf("NO");
        return 0;
    }
    k=2*sum/n/(n+1);
    for(int i=0;i<n;i++)
    {
        if(i==n-1)
            dis[i]=a[0]-a[i];
        else
            dis[i]=a[i+1]-a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(k-dis[i]<0||(k-dis[i])%n!=0)
        {
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define inf 1e12
#define eps 1e-10
struct point{
	double x,y,z;
	point(double x,double y,double z):x(x),y(y),z(z){}
	point(){}
	point operator +(const point &a) {return point(x+a.x,y+a.y,z+a.z);}
	point operator -(const point &a) {return point(x-a.x,y-a.y,z-a.z);}
	point operator *(const double a) {return point(x*a,y*a,z*a);}
	void make(){	cin>>x>>y>>z; }
	void print(){ cout<<x<<' '<<y<<' '<<z<<endl; }
	double dot(point &a){ return x*a.x+y*a.y+z*a.z; }
	point cross(point &a){ return point( y*a.z-z*a.y , z*a.x - x*a.z , x*a.y - y*a.x ); }
	double norm(){ return x*x + y*y + z*z ; }
	double abs(){ return sqrt(norm()); }
};
double dot(point &a,point &b){	return a.x*b.x+a.y*b.y+a.z*b.z; }
point cross(point &a,point &b){
	return point( a.y*b.z - a.z*b.y , a.z*b.x - a.x*b.z , a.x*b.y - a.y*b.x );
}


int main(){
	point s,t;
	point v[3];
	s.make();
	t.make();
	for(int i = 0 ; i < 3 ; i++ ) v[i].make();
	s = s-v[0];
	t = t-v[0];
	v[1] = v[1] - v[0];
	v[2] = v[2] - v[0];
	v[0] = v[0] - v[0];
	point n = v[1].cross(v[2]);
	n =  n*(1.0/n.abs() );

	bool flag = false;
	point d = s-t;
	if( abs( n.dot( d ) ) > eps ){
		double a = n.dot( s );
		double b = n.dot( t );
		if( a * b < eps ){
			point m = ( s* ( abs(b)/ ( abs(a) + abs(b)  )  )  )+ ( t * ( abs(a)/ ( abs(a) + abs(b) ) ) );  
			double tri = v[1].cross(v[2]).abs();
			double tri_m = 0;
			for(int i=0;i<3;i++){
				point aa  = v[i]-m;
				point bb  = v[(i+1)%3]-m;
				tri_m += aa.cross( bb ).abs();
			}
			if( abs( tri_m - tri ) < eps ) flag = true;
		}
	}
	if(flag){
		cout<<"MISS"<<endl;
	}else {
		cout<<"HIT"<<endl;
	}

	return 0;
}



Measured memory_bytes: 3268
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int n;

int main() {
    cin >> n;
    int cnt = 0;
    rep(i,n) {
        int p; cin >> p;
        if (i != p-1) cnt++;
    }
    if (cnt <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

int N, u, v, w, c[100100];
vector<pair<int, int> > V[100100];
bool vis[100100];

void dfs(int a, int b) {
    c[a] = b;
    vis[a] = true;
    for(int i=0; i<(int)V[a].size(); i++) {
        int nxt = V[a][i].first;
        int len = V[a][i].second;
        if (!vis[nxt]) {
            dfs(nxt, (b+len)%2);
        }
    }
}

int main () {
    cin >> N;
    for(int i=0; i<N-1; i++) {
        cin >> u >> v >> w;
        V[u].push_back(make_pair(v, w));
        V[v].push_back(make_pair(u, w));
    }
    dfs(1, 0);
    for(int i=1; i<=N; i++)
        cout << c[i] << endl;
	return 0;
}

Measured memory_bytes: 8448
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    if N == 1:
        print('Hello World')
    else:
        A = I()
        B = I()
        print(A + B)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<ll> a(n),sum(n+1,0);
	rep(i,n){
		cin>>a[i];
		sum[i+1]=sum[i]+a[i];
	}
	vector<vector<ll>> dp(n,vector<ll>(n+1,-1));
	//[l,r)のスライムを1つにまとめる時の最小コスト
	//dp[l][l+1]=a[l]
	function<ll(int,int)> dfs=[&](int l,int r){
		if(dp[l][r]>=0) return dp[l][r];
		if(r==l+1) return 0ll;
		ll ret=inf;
		FOR(k,l+1,r){
			chmin(ret,dfs(l,k)+dfs(k,r)+sum[r]-sum[l]);
		}
		return dp[l][r]=ret;
	};
	cout<<dfs(0,n)<<endl;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef pair<int,int> pii;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
template<class Type> void line(const Type &a){int cnt=0;for(auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int k,x;
	cin>>k>>x;
	
	if(k*500>=x) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 256
N, M = list(map(int, input().split()))
Hs = list(map(int, input().split()))
flg_list = [0] * N
for j in range(M):
    ai, bi = list(map(int, input().split()))
    ai -= 1
    bi -= 1
    if Hs[ai] > Hs[bi]:
        flg_list[bi] += 1
    elif Hs[ai] < Hs[bi]:
        flg_list[ai] += 1
    else:
        flg_list[ai] += 1
        flg_list[bi] += 1

print(flg_list.count(0))


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

using namespace std;

int main(void)
{
	int n, m;
	while (cin >> n >> m){
		if (n == 0 && m == 0) break;
		vector < pair <int, int> > data(m);
		pair <int, int> edge[20050];
		for (int i = 0; i < 20050; i++){
			edge[i].first = edge[i].second = -1;
		}
		int t, s, d;
		for (int i = 0; i < m; i++){
			cin >> t >> s >> d;
			data[i].first = t;
			data[i].second = i;
			edge[i].first = s;
			edge[i].second = d;
		}
		sort(data.begin(), data.end());

		bool infect[20050] = {false};
		infect[1] = true;
		for (int i = 0; i < m; i++){
			int from = edge[data[i].second].first;
			int goal = edge[data[i].second].second;
			if (infect[from]){
				infect[goal] = true;
				// cout << goal << " is infect" << endl;
			}
		}

		int ret = 0;
		for (int i = 0; i <= 20050; i++){
			if (infect[i]) ret++;
		}
		cout << ret << endl;
	}

	return 0;
}

Measured memory_bytes: 1540
#!/usr/bin/env python3
sx, sy, tx, ty = map(int, input().split())
x = tx - sx
y = ty - sy
s = ''
s += 'U' * y + 'R' * x
s += 'D' * y + 'L' * x
s += 'L' + 'U' * (y+1) + 'R' * (x+1) + 'D'
s += 'R' + 'D' * (y+1) + 'L' * (x+1) + 'U'
print(s)


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

    //組み合わせの数nCrを計算
    int combi(int n, int r){
        int num = 1;
        for(int i = 1; i <= r; i++){
            num = num * (n - i + 1) / i;
        }
        return num;
    }

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

  int L = S.size()/2;
  for(int i =0;i<L; i++){
    if(S.at(i) != S.at(S.size()-1-i)){
      cout << "No" << endl;
      return 0;
    }
  }

  L = S.size()/4;
  for (int i =0;i<L;i++){
    if(S.at(i) != S.at(S.size()/2-1-i)){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
}

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

static const int mod = 1e9 + 7;

int fast_power(int a, int b) {
  long long p = 1, q = a;
  while (b) {
    if (b & 1)
      p = p * q % mod;
    q = q * q % mod;
    b >>= 1;
  }
  return p;
}

int c(int n, int k, const vector<int> &f, const vector<int> &g) {
  int res = 1;
  for (int i = 1; i <= k; i++)
    res = 1LL * res * f[i] % mod;
  res = 1LL * res * g[k - 1] % mod;
  return res;
}

int main() {
  int n, a, b;
  scanf("%d %d %d", &n, &a, &b);
  
  int ans = (fast_power(2, n) + mod - 1) % mod;

  vector<int> f(b + 1), g(b + 1);
  f[0] = 1, g[0] = n;
  for (int i = 1; i <= b; i++) {
    f[i] = fast_power(i, mod - 2);
    g[i] = 1LL * g[i - 1] * (n - i) % mod;
  }

  ans = (ans - c(n, a, f, g) + mod) % mod;
  ans = (ans - c(n, b, f, g) + mod) % mod;
  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 1792
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input!{
      s: chars,
      k: usize,
    }

    let n = s.len();

    let mut start = 0;
    let mut end = n-1;
    if s[0] == s[n-1] {
        let c = s[0];
        while start < n && s[start] == c {
            start += 1;
        }

        if start == n {
            return puts!("{}\n", (n*k)/2);
        }

        while s[end] == c {
            if end == 0 {
                break;
            }
            end -= 1;
        }
    }
    end += 1;
    let start_num = start;
    let end_num = n-end;

    // debug!(start_num, end_num, start, end);

    let mut ans = 0;
    let mut cnt = 0;
    for i in start+1..end {
        if s[i] == s[i-1] {
            cnt += 1;
        } else {
            ans += (cnt+1)/2;
            cnt = 0;
        }
    }
    ans += (cnt+1)/2;
    ans *= k;
    ans += (start_num + end_num)/2 * (k-1);
    ans += start_num/2;
    ans += end_num/2;
    puts!("{}\n", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    char s[n];
    cin>>s;
    int co=0;
    for(int i=0;i<n-2;i++){
        if('A'==s[i]&&'B'==s[i+1]&&'C'==s[i+2]){
            co+=1;
        }
    }
    cout<<co;
}


Measured memory_bytes: 888
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

int main(void){
 int A,B;
 cin>>A>>B;
 cout<<max({A+B,A+A-1,B+B-1})<<endl;
 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI (acos(-1))
#define ct cout<<
#define cn cin>>
#define spc <<" "<<
#define nl puts("")
#define _fl(x) puts("FLAG " #x);
#define  _(x)  cout<< #x <<" is "<< x <<endl;
#define fs first
#define sc second
#define pb push_back
#define all(v)  (v).begin(), (v).end()
#define _109 (1000000000)
#define _0(arr) memset(arr,0,sizeof ( arr ) )
#define _1(arr) memset(arr,-1,sizeof ( arr ) )
#define _ninp(n,arr) for(int i=0; i<n;i++)cin>>arr[i];
#define _nout(n,arr) for(int i=0; i<n;i++)cout<<arr[i]<<" \n"[i==n-1];
double _eps=1e-6;


int main() {
   
   int n,m;
   cn n>>m;
   
      int cntt=0;
   for (int i = 0; i < m; ++i)
   {
   	 int a;cn a;
   	 cntt+=a;
   }

   if(cntt>n)ct "-1";
   else ct n-cntt;

   nl;


    return 0;
}


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

using namespace std;

const int maxn = 2100;

int n,m,q,dow[maxn][maxn],ri[maxn][maxn],a[maxn][maxn];

int main() {
    //freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++) {
        string s;
        cin>>s;
        for (int j=1;j<=m;j++)
            if (s[j-1]=='1') a[i][j]=1;
    }
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++)
            if (a[i][j] == 1 && a[i+1][j]==1) dow[i][j]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++)
            if (a[i][j] == 1 && a[i][j+1]==1) ri[i][j]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            dow[i][j] += dow[i-1][j] + dow[i][j-1] - dow[i-1][j-1];
            ri[i][j] += ri[i-1][j] + ri[i][j-1] - ri[i-1][j-1];
        }
    for (int i=1;i<=q;i++) {
        int x0,x1,y0,y1;
        cin>>x0>>y0>>x1>>y1;
        int all = a[x1][y1] - a[x1][y0-1] - a[x0-1][y1] + a[x0-1][y0-1];
        x1--;
        int allDOW = dow[x1][y1] - dow[x1][y0-1] - dow[x0-1][y1] + dow[x0-1][y0-1];
        x1++; y1--;
        int allRI = ri[x1][y1] - ri[x1][y0-1] - ri[x0-1][y1] + ri[x0-1][y0-1];
        cout<<all - allDOW - allRI<<endl;
    }
}


Measured memory_bytes: 52992