akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  ll n,m;
  cin>>n>>m;
  cout << min(n,m/2)+(m-min(n,m/2)*2)/4 << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
A = [int(x) for x in input().split()]
colored = [False] * 8
cnt = 0
super= 0
for a in A:
    if 3200 <= a:
        super += 1
        continue
    rank = a // 400
    if not colored[rank]:
        colored[rank] = True
        cnt += 1
mn = 1 if cnt == 0 and super != 0 else cnt
mx = cnt + super
print(mn, mx)
      

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO 自動生成されたメソッド・スタブ
		 InputStreamReader is = new InputStreamReader(System.in);
		 BufferedReader br = new BufferedReader(is);
		 int count = 1;
		 int input = Integer.parseInt(br.readLine());
		 while (input != 0) {
			 System.out.println("Case"+" "+count+": "+input);
			 input = Integer.parseInt(br.readLine());
			 count++;
		 }
		
	
	}

}


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

#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//以降 cin の入力元が 'input.txt' になる
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());
 
bool visited[500][500];
int b;
int W;
char s[500][500];
int h,w; 
void dfs(int x,int y){
    visited[x][y] = true;
    if(s[x][y] == '#')b++;
    else W++;
    for(int i=0;i<8;i+=2){
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if(nx < 0 || nx >= h || ny < 0 || ny >= w)continue;
        if(s[x][y] == s[nx][ny])continue;
        if(visited[nx][ny])continue;
        dfs(nx,ny);
    }
}
signed main()
{
    gearup;
    cin >> h >> w;
    rep(i,h)rep(j,w)cin>>s[i][j];
    ll res = 0;
    rep(i,h)rep(j,w){
        if(s[i][j] == '.')continue;
        if(visited[i][j])continue;
        b = 0;W = 0;
        dfs(i,j);
        res += b * W;
    }
    out(res);
}


Measured memory_bytes: 13804
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
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;
}
int main(){
    ll n;cin >> n;
    vl v(n);
    rep(i,n)cin >> v[i];
    rep(i,n)v[i]-=(i+1);
    sort(all(v));
    ll x,y=0;
    if(n%2==1)x=v[n/2];
    if(n%2==0){
        x=(v[n/2]+v[n/2-1])/2;
        if((v[n/2]+v[n/2-1])%2==1)y=x+1;
    }
    ll ans1=0,ans2=0;
    rep(i,n)ans1+=abs(v[i]-x);
    rep(i,n)ans2+=abs(v[i]-y);
    cout << min(ans1,ans2) <<endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

ll power(ll a,ll b,ll mod){
    ll ret=1;
    if(b>0){
        ret = power(a,b/2,mod);
        if(b%2==0)ret = (ret*ret)%mod;
        else ret = (((ret*ret)%mod)*a)%mod;
    }
    return ret;
}
int n,x,m;
int l[20],r[20],s[20];


int solve(int data[9]){
    int ret=0;
    int rui[9]={};
    rep(i,n+1){
        rui[i]=data[i];
        ret+=data[i];
    }
    rep(i,n){
        rui[i+1]=rui[i]+rui[i+1];
    }
    rep(i,m){
        if( rui[r[i]]-rui[l[i]-1]!=s[i] )return -1;
    }
    return ret;
}
int main(){
    int ans[9]={};
    int num=-1;
    cin>>n>>x>>m;
    int v=power(x+1,n,1e8);
    rep(i,m){
        cin>>l[i]>>r[i]>>s[i];
    }
    
    rep(i,v){
        int data[9]={};
        int z=i;
        rep(j,n){
            data[n-j]=z%(x+1);
            z/=(x+1);
        }
        int res;
        if( (res = solve(data))!=-1 && num<res ){
            num=res;
            rep(i,9)ans[i]=data[i];
        }
    }
    if(num==-1)cout<<-1<<endl;
    else{
        rep(i,n){
            if(i)cout<<" ";
            cout<<ans[i+1];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 1164
N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
sum = [0] * (N+1)
for i in range(1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		sum[i+1] = sum[i] + 1
	else:
		sum[i+1] = sum[i]
# print(sum)


for i in range(Q):
	print(sum[R[i]] - sum[L[i]])


Measured memory_bytes: 14244
N = int(input())
X = sorted(list(map(int, input().split(' '))))

min_e = 10 ** 9
for p in range(X[0], X[-1] + 1):
    e = sum([(x - p) ** 2 for x in X])
    min_e = min(min_e, e)

print(min_e)


Measured memory_bytes: 3060
n = int(input())

tlist = [list(map(int,input().split())) for i in range(n)]

a = tlist[0][0]
b = tlist[0][1]

for t in tlist:
    multi = max((a//t[0]) + (a%t[0] > 0), (b//t[1]) + (b%t[1] > 0))
    # print('multi', multi)
    # print('a b', a, b)
    a = t[0]*multi
    b = t[1]*multi

print(a + b)


Measured memory_bytes: 3188
package main

import (
	"fmt"
	"bufio"
	"os"
)
func ri() (n int) {
	sc.Scan()
	for _, v := range sc.Bytes() {
		n = n*10 + int(v-48)
	}
	return
}
var sc = bufio.NewScanner(os.Stdin)
func main() {
	sc.Split(bufio.ScanWords)
	var n int
	fmt.Scan(&n)
	var sq = make([]int, n)
	xor := 0
	for i := range sq {
		sq[i] = ri()
		xor = xor ^ sq[i]
	}
	for i := range sq {
		fmt.Print(sq[i] ^ xor)
		fmt.Print(" ")
	}
}


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

int main () {
  double W, H, x, y;
  cin >> W >> H >> x >> y;
  
  double ans = W * H / 2;
  int zo;
  if (x == W/2 && y == H/2) zo = 1;
  else zo = 0;
  
  cout << ans << " " << zo << endl;
}


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

const int moder = 1e9 + 7;

int n;

int main(){
	scanf("%d", &n);
	int ret = 1;
	for (int i = 1; i <= n; ++ i){
		ret = 1ll * ret * i % moder;
	}
	return printf("%d\n", ret), 0;
}

Measured memory_bytes: 256
N=int(input())
a=[]
for i in range(2):
    a.append(list(map(int,input().split())))
c=[]
for i in range(N):
    count=0
    for j in range(N):
        if j<i:
            count+=a[0][j]
        else:
            count+=a[1][j]
        if i==j:
            count+=a[0][j]
    c.append(count)
print(max(c))
            

Measured memory_bytes: 3064
#include <stdio.h>
#define N 2000

int solve(int,int);
int A[N],n=0;

int main()
{
  int i,q,m;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m);
    if(solve(0,m)==1) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

int solve(int i,int m)
{
  int res;
  if(m == 0) return 1;
  if(i >= n) return 0;
  res = solve(i+1,m) || solve(i+1, m-A[i]);
  return res;
}



Measured memory_bytes: 2140
from collections import deque

n, m = map(int, input().split())

maze = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    maze[a-1].append(b-1)
    maze[b-1].append(a-1)

seen = [0 for i in range(n)]

mile = [-1 for i in range(n)]

q = deque()

q.append(0)
seen[0] = 1

while len(q) != 0:
    cur = q.popleft()

    for nx in maze[cur]:
        if not seen[nx] == 1:
            mile[nx] = cur+1
            seen[nx] = 1
            q.append(nx)

print('Yes')
for i in range(n-1):
    print(mile[i+1])


Measured memory_bytes: 37868
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll x;
int main() {
	cin>>x;
	ll det = x / 11;
	ll r = 0;
	if (x % 11) {
		if (x % 11 <= 6) r = 1;
		else r  =2 ;
	}
	cout<<det*2LL+r<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

int main()
{
  int n;
  cin>>n;
  int v[n],c[n];
  rep(i,n) cin>>v[i];
  rep(i,n) cin>>c[i];

  int ans=0;
  rep(i,n)
  {
    if(v[i]>c[i]) ans+=(v[i]-c[i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n,m = map(int, input().split())
s = [tuple(map(int,input().split())) for _ in range(n)]
c = [tuple(map(int,input().split())) for _ in range(m)]
for i in range(n):
  mini = 0
  m_i = 0
  for j in range(m):
    dis = abs(s[i][0]-c[j][0])+abs(s[i][1]-c[j][1])
    if j==0:
      mini, m_i = dis, j+1
      continue
    elif mini > dis:
      mini, m_i = dis, j+1
  print(m_i)

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

const int N = 100005;

int n, m;
int par[N], sum[N], a[N], d[N];
string s;

int find(int x) {
	return (x == par[x]) ? x : par[x] = find(par[x]);
}

void join(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	sum[x] += sum[y], sum[y] = 0, sum[x] %= 26, par[y] = x;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> s, s = 'a' + s + 'a';
	n = s.size();
	for (int i = 1; i < n; ++i) {
		a[i] = s[i] - 'a';
		d[i] = a[i] - a[i - 1];
		if (d[i] < 0) d[i] += 26;
	}
	for (int i = 1; i < n; ++i) par[i] = i, sum[i] = d[i];
	for (int i = 1; i < n; ++i) join(i, n - i);
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		int l, r; cin >> l >> r; join(l, r + 1);
	}
	for (int i = 1; i < n; ++i) {
		if (sum[find(i)]) {
			cout << "NO"; return 0;
		}
	}
	cout << "YES";
}

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

int n, k, s;
int mod = 1e9;

int main() {
	scanf("%d%d%d", &n, &k, &s);
	if (s == mod) mod--;
	for (int i = 1; i <= k; i++) 
		printf("%d ", s);
	for (int i = k + 1; i <= n; i++)
		printf("%d ", mod);
	printf("\n");
	return 0;
}


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

using namespace std;

int main(int argc, char *argv[]) {
	int N, A, B;
	cin >> N >> A >> B;

	string num_str(to_string(N));
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		int digit_sum = 0;
		string num_str(to_string(i));
		for (int i = 0; i < num_str.size(); i++) {
			digit_sum += (num_str[i] - '0');
		}
		if (digit_sum >= A && digit_sum <= B) {
			answer += i;
		}
	}

	cout << answer << endl;
	return 0;
}


Measured memory_bytes: 256
m[31][50];main(n,p,d,x){long long a[50],b;for(;scanf("%d",&n),n;){memset(m,0,6200);for(p=0;p<n;a[p]=1LL<<p,p++)for(scanf("%d",&x);x;x--)scanf("%d",&d),m[d][p]=1;for(d=1;d<31;d++){for(b=p=0;p<n;p++)if(m[d][p])b|=a[p];for(p=0;p<n;p++)if(m[d][p]&&(a[p]=b)==(1LL<<n)-1){printf("%d\n",d);goto s;}}puts("-1");s:;}exit(0);}

Measured memory_bytes: 616
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    ll N,M;
    cin >> N >> M;
    ll i;
    ll X[M];
    for(i=0;i<M;i++){
      cin >> X[i];
    }
    sort(X,X+M);
    ll dist[M-1];
    for(i=0;i<M-1;i++){
      dist[i]=X[i+1]-X[i];
    }
    sort(dist,dist+M-1);
    ll ans=0;
    for(i=0;i<M-N;i++){
      ans+=dist[i];
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
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; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;

int main(){
 int N, K; cin >> N >> K;
    int ans = 0;
    deque<int> deq;
    vector<int> v(N,0);
    rep(i,N){
        cin >> v[i];
    }
    // 左から取る個数
    for (int l = 0; l <= K; l++){
        // 右から取る個数
        for (int r = 0; r <= K; r++){
            // 取る回数がKを越した場合はNG
            if (l + r > K) continue;
            int d = K - l - r;
            priority_queue<int, vector<int>, greater<int>> tmp;
            // 左から取る
            rep(i,l){
                // dequeの右端に達した場合
                if (i >= N) break;
                tmp.push(v[i]);
            }
            // 右から取る
            rep(i,r){
                int index = N-1-i;
                // dequeの左端もしくはすでに左から取られている場合
                if (index < 0 || index <= l) break;
                tmp.push(v[index]);
            }
            // 手から宝石をつめる
            rep(i,d){
                // 手に持っていない場合
                if (tmp.empty()) break;
                // 価値は正の場合はつめない
                if (tmp.top() >= 0) break;
                tmp.pop();
            }

            int now = 0;
            while (!tmp.empty()){
                now += tmp.top(); tmp.pop();
            }

            ans = max(now, ans);
        }
    }


    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000

int A[MAX], n;

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

int main(void) {
  int i, q;

  scanf("%d", &n);
  for(i=0; i<n; i++) scanf("%d",&A[i]);
  q = partition(0,n-1);

  for(i=0; i<n; i++) {
    if(i) printf(" ");
    if(i==q) printf("[");
    printf("%d",A[i]);
    if(i==q) printf("]");
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 2112
import Control.Monad
import Control.Monad.ST
import qualified Data.Array as A
import qualified Data.Array.ST as ST
import qualified Data.Array.Unboxed as AU
import Data.Bits
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.Int
import qualified Data.IntMap as IM
import Data.List
import qualified Data.Map as M
import Data.Maybe
import Data.Ord
import qualified Data.Set as S
import Data.Time
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

putListWithSpace :: Show a => [a] -> IO ()
putListWithSpace [a] = putStr $ show a
putListWithSpace (a:as) = do
  putStr $ show a
  putStr " "
  putListWithSpace as

main = do
  readInt
  as <- readInt
  print $ solve as

solve as = sum as - length as

Measured memory_bytes: 1020
using System;
using System.Linq;

namespace ABC083_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var cl = input[0] + input[1] > input[2] + input[3];
            var ce = input[0] + input[1] == input[2] + input[3];
            Console.WriteLine(ce ? "Balanced" : (cl ? "Left" : "Right"));
        }
    }
}


Measured memory_bytes: 13268
#import math
import collections
#n,k = map(int, input().split( ))
#A = list(map(int, input().split( )))
n = int(input())
A = list(map(int, input().split( )))
c = collections.Counter(A)

a = c.most_common()[0][1]
if a != 1:
  print('NO')
else:
  print('YES')

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

typedef long long ll;
typedef long double ld;
#define size(a) int((a).size())
#define present(c, x) (c.find(x) != c.end()) 

template <class T>
void printArray(vector<T> arr) {for (T a: arr) cout << a << " ";cout << '\n';}
void printVerdict(bool verdict) {cout << (verdict ? "YES": "NO") << '\n';}
void printDecimal(double d) {printf("%.9f\n", d);}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	string s; cin >> s;
	vector<int> position;
	for (int i = 0; i<n; i++) {
		if (s[i] == 'A') position.push_back(i);
	}
	int cnt = 0;
	for (int pos: position) {
		if (!s.substr(pos, 3).compare("ABC")) cnt++;
	}
	cout << cnt << '\n';
}



Measured memory_bytes: 3664
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
 
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
 
    int counter = 0;
    if (a <= 0) {
        counter += -a * c + d + b * e;
    }
    else {
        counter += (b-a) * e;
    }
     
    cout << counter << endl;
}


Measured memory_bytes: 3112
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 100000000;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
const ll MAX = 200010;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,h;
    cin >> a >> b >> h;
    PRINT((a+b)*h/2);
}



Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <deque>

using std::cin, std::cout, std::endl, std::string;
using ll = long long;

#define rep(countName, left, right, up) for (ll countName = left; countName < right; countName += up)
#define REP(countName, end) for (ll countName = 0; countName < end; countName++)
#define rev(countName, right, left, down) for (ll countName = right - 1; countName >= left; countName -= down)
#define REV(countName, end) for (ll countName = end - 1; countName >= 0; countName--)

ll solve1(int n, string s)
{
    ll R = 0, G = 0, B = 0, ans;

    REP(i, n)
    {
        switch (s[i])
        {
        case 'R':
            R++;
            break;
        case 'G':
            G++;
            break;
        case 'B':
            B++;
            break;
        }
    }

    ans = R * G * B;
    rep(i, 0, n - 2, 1)
    {
        rep(j, i + 1, n - 1, 1)
        {
            ll k = 2 * j - i;
            if (s[i] != s[j] && s[j] != s[k] && s[k] != s[i] && k < n)
            {
                //cout << s[i] << s[j] << s[k] << endl;
                ans--;
            }
        }
    }
    return ans;
}

int main(void)
{
    int n;
    string s;
    cin >> n >> s;
    cout << solve1(n, s) << endl;
    return 0;
}

Measured memory_bytes: 3632
N,M=map(int,input().split())
from collections import defaultdict
f = defaultdict(lambda:1)

mod=10**9+7

for i in range(M):
    f[int(input())]=0

b = defaultdict(int)
b[0]=1

for i in range(1,N+1):
    if f[i]==1:
        b[i]=(f[i-1]*b[i-1]+f[i-2]*b[i-2])%mod

print(b[N])


Measured memory_bytes: 24492
#include <iostream>
using namespace std;
int main(void){
 int A,B;
 cin>>A>>B;
 if(A>B){
if(B==1){
    cout<<"Bob"<<endl; 
    }
 else{
cout<<"Alice"<<endl;     
 }
 }
else if(B>A){
if(A==1){
    cout<<"Alice"<<endl;
}
else {
cout<<"Bob"<<endl;     
}
}    
else{
 cout<<"Draw"<<endl;   
}
}

Measured memory_bytes: 3624
#include<stdio.h>
#define N 100
#define INF 100000000
int n,M[N][N],d[N],Q[N],tail = 0,head = 0;

void push(int a) {
  Q[tail] = a;
  tail ++;
}
int pop() {
  int a;
  a = Q[head];
  head++;
  return a;
}

void bfs(int s) {
  int i,u,v;

  push(s);
  for(i = 0;i < n;i++) d[i] = INF;
  d[s] = 0;

  while(tail != head) {
    u = pop();
    for(v = 0;v < n;v++) {
      if(M[u][v] == 0) continue;
      if(d[v] != INF) continue;
      d[v] = d[u] + 1;
      push(v);
    }
  }
  for(i = 0;i < n;i++) {
    if(d[i] == INF) d[i] = -1;
    printf("%d %d\n",i + 1,d[i]);
  }
}

int main() {
  int i,j,u,k,v;

  scanf("%d",&n);
  for(i = 0;i < n;i++) {
    for(j = 0;j < n;j++) M[i][j] = 0;
  }

  for(i = 0;i < n;i++) {
    scanf("%d%d",&u,&k);
    u--;
    for(j = 0;j < k;j++) {
      scanf("%d",&v);
      v--;
      M[u][v] = 1;
    }
  }

  bfs(0);

  return 0;
}



Measured memory_bytes: 2076
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;


typedef long long ll;
const int MAX_V = 210;
const int INT_INF = 1<<30;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
struct edge {
	int to, cap, cost, rev;
};
int V;
vector<edge> G[MAX_V];
int h[MAX_V], dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
	G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1});
}

int min_cost_flow(int s, int t, int f) {
	int res = 0;
	fill_n(h, V, 0);
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P>> que;
		fill_n(dist, V, INT_INF);
		dist[s] = 0;
		que.push(P(0, s));
		while (!que.empty()) {
			P p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			for (int i = 0; i < G[v].size(); i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to], e.to));
				}
			}
		}
		if (dist[t] == INT_INF) {
			return -1;
		}
		for (int v = 0; v < V; v++) {
			h[v] += dist[v];
		}
		int d = f;
		for (int v = 0; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

const int MAX_N = 105;
int N;
int W[MAX_N][MAX_N], E[MAX_N][MAX_N];
bool F[MAX_N][MAX_N], F2[MAX_N][MAX_N];

int main(int argc, char *argv[]) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(W[i][j]));
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(E[i][j]));
		}
	}
	int min_f = 0, f = 0;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			F[i][j] = (s[j] == 'o');
			if (F[i][j]) {
				min_f = min(min_f, -E[i][j]);
				f += E[i][j];
			}
		}
	}
	min_f *= -1;
	V = (N+1)*2;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				add_edge(i, N+j, 1, -E[i][j]+min_f);
			} else {
				add_edge(i, N+j, 1, W[i][j]+min_f);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		add_edge(N*2, i, 1, 0);
	}
	for (int i = 0; i < N; i++) {
		add_edge(N+i, N*2+1, 1, 0);
	}
	f += min_cost_flow(N*2, N*2+1, N);
	f -= min_f*N;
	int c = 0;
	vector<T> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == G[i][j].cap) {
				c++;
				q.push_back(T(i, j, F[i][j]));
			}
		}
	}
	printf("%d\n%d\n", f, c);
	for (T t: q) {
		printf("%d %d %s\n", get<0>(t)+1, get<1>(t)+1, get<2>(t) ? "erase" : "write");
	} 
    return 0;
}

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

int main(){
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll ans=max(max(a*c,a*d),max(b*c,b*d));
  if((a<=0 && b>=0)||(c<=0 && d>=0)) ans=max(0LL,ans);
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
n = int(input())
a = [0] + list(map(int, input().split()))
ball = [0] * (n+1)

for i in range(n,0,-1):
  s = sum(ball[i: :i])
  if s % 2 == a[i]:
    ball[i] = 0
  else:
    ball[i] = 1

ans = []
for i in range(1,n+1):
  if ball[i] == 1:
    ans += [str(i)]
    
if ans:
  print(len(ans))
  print(" ".join(ans))
else:
  print(0)
  
  




Measured memory_bytes: 17196
/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")*/
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;


#define int long long
// #define double ld
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
const int N = 5e5 + 5;
int f[N];

void modify(int v, int val) {
    for (int i = v; i < N; i |= (i + 1))
        f[i] += val;
}
int sum(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}
int get(int l, int r) {
    return sum(r) - sum(l - 1);
}


signed main() {
    srand(time(0));
    accell();
    int n, d, a;
    cin >> n >> d >> a;
    vector<pair<int, int> > vec(n);
    for (int i = 0; i < n; ++i) {
        cin >> vec[i].first >> vec[i].second;
    }
    sort(all(vec));
    int r = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        pair<int, int>x = {vec[i].first - 2 * d, 0LL};
        int lf = lower_bound(all(vec), x) - vec.begin();
        int cur = vec[i].second - get(lf, i);
        if (cur <= 0)
            continue;
        int res = (cur + a - 1) / a;
        modify(i, res * a);
        ans += res;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 4992
// AOJ 0571: JJOOII
// 2017.9.1 bal4u@uu
// 2017.11.28

#include <stdio.h>

char s[1000005];

int main()
{
	int j, o, i, ans;
	char *p;

	fgets(p=s, sizeof(s), stdin);
	j = o = i = ans = 0;
	while (*p > ' ') {
		if (*p++ != 'J') continue;
		j = 1;
		while (*p == 'J') j++, p++;
		if (*p != 'O') continue;
		p++, o = 1;
		while (*p == 'O') o++, p++;
		if (*p != 'I') continue;
		p++, i = 1;
		while (*p == 'I') i++, p++;
		if (j >= o && i >= o && o > ans) ans = o;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2828
#include<bits/stdc++.h>
#define ff first
#define ss second
#define IO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
ll mx = 1e18;

int main() {
    IO;
    int n;
    cin >> n;
    vector<ll> a(n);
    for(ll &x: a)
        cin >> x;
    sort(a.begin(), a.end());
    ll res = 1;
    for(ll &x: a){
        if((__int128) res * x > (__int128) mx) {
            res = -1;
            break;
        } else
            res *= x;
    }
    cout << res << '\n';
    return 0;
}


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

int main(void){

    vector<bool> is_prime(100001);
    vector<int> prime;
    vector<int> sums(100001);
     
    for (int n = 2; n < 100002; ++n) {
        if (n == 2 || n == 3) {
            is_prime[n] = true;
            prime.push_back(n);
        }
        
        is_prime[n] = true;
        for (auto i : prime) {
            if (i > n / 2) { 
                break;
            }
            if (n % i == 0) {
                is_prime[n] = false;
                break;
            } 
        }
        
        if (is_prime[n]) {
            prime.push_back(n);
        }
    }
    
    for (int i = 3; i < 100002; ++i) {
        sums[i] = sums[i - 1];
        if (is_prime[i] && is_prime[(i + 1) / 2]) {
            sums[i] += 1; 
        }
    }

    int Q;
    cin >> Q;
    
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        
        cout << sums[r] - sums[l - 1] << endl;
    }
    
}


Measured memory_bytes: 1152
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        char[] s = sc.next().toCharArray();
        List<Integer> one = new ArrayList<>();
        List<Integer> zero = new ArrayList<>();
        int oneCnt = 0;
        int zeroCnt = 0;
        if (s[0] == '1') {
            oneCnt++;
        } else {
            zeroCnt++;
            one.add(0);
        }
        for (int i = 1; i < n; i++) {
            if (s[i] == '1') {
                oneCnt++;
                if (zeroCnt != 0) {
                    zero.add(zeroCnt);
                    zeroCnt = 0;
                }
            } else {
                zeroCnt++;
                if (oneCnt != 0) {
                    one.add(oneCnt);
                    oneCnt = 0;
                }
            }
        }
        if (oneCnt != 0) {
            one.add(oneCnt);
        } else if (zeroCnt != 0) {
            zero.add(zeroCnt);
            one.add(0);
        }

        if (zero.isEmpty() || zero.size() == 1 && one.get(0) == 0 && one.get(1) == 0) {
            System.out.println(s.length);
            return;
        }
        long oneSum = 0;
        long zeroSum = 0;
        for (int i = 0; i < Math.min(k + 1, one.size()); i++) {
            oneSum += one.get(i);
        }
        for (int i = 0; i < Math.min(k, zero.size()); i++) {
            zeroSum += zero.get(i);
        }
        long ans = zeroSum + oneSum;
        for (int i = 1; i < zero.size() - k + 1; i++) {
            zeroSum += zero.get(i + k - 1) - zero.get(i - 1);
            oneSum += one.get(i + k) - one.get(i - 1);
            ans = Math.max(zeroSum + oneSum, ans);
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 42972
# 全部やればよい
N = int(input())
W = [int(x) for x in input().split()] # 0-indexed

s = 0
W_cum = []
for w in W:
  s += w
  W_cum.append(s)

total = s

INF = 10**10
answer = INF

for T in range(1,N):
  s1 = W_cum[T]
  s2 = total - s1
  score = abs(s1-s2)
  if score < answer:
    answer = score

print(answer)

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

#define Bye return 0
#define ll long long

using namespace std;

void solve(){
    int n; cin>>n;
    
    set<int> a;
    bool exists = false;
    for (int i=0; i<n; i++){
        int e; cin>>e;
        if(a.count(e) == 1) exists = true;
        else a.insert(e);
    }
    cout<<(exists?"NO":"YES")<<endl;
}

int main(){
    solve();
    Bye;
}

Measured memory_bytes: 12948
import java.util.*;
import java.util.Map.Entry;
 
 
 
public class Main{
	
	
	
	public static long A;
	public static long answer = 0;
	public static long MOD=1000000007;
	

 
	
	//最大公約数・最小公倍数（セットで使う）
	public static long gcm(long a, long b) {
		long result = a;
		long k = 0;
		long n = b;
		do {
			k = result % n;
			result = n;
			n = k;
		} while(k != 0);
		return result;
	}
	
	public static long lcm(long a, long b) {
		long g;
		g = gcm(a, b);
		return a/g*b;
	}
	
	static long gcd(long a, long b) {
		if (b == 0) {
			return a;			
		}
		return gcd(b, a % b);
	}
	
	//等差数列
	static long tousasum(int n) {
		return (long)n*((long)n+1)/2;
	}
 
 
 
	//素数判定
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
		return true;
	}
 
 
	//倍数判定（10進数以外のときに有用）
	static boolean isMultiple (String s, int base, int m) {
		int temp = 0;
		for (int i=0; i<s.length(); i++) {
			temp = (temp*base+Character.getNumericValue(s.charAt(i)))%m;
		}
		if (temp==0) {return true;}
		return false;
	}
 
 
	//階乗
	static long factorial (int k) {
		long sum = 1;
		for(int i=1;i<=k;i++) {
			sum = (sum*i)%MOD;
		}
		return sum;
		
	}
 
 
	//進数変換
	static String toNbase (String sm, int m, int n) {
		return Long.toString(Long.parseLong(sm,m),n);
	}
	
	public static final long gcd_n(long[] param) {
	    final int len = param.length;
	    long g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
	    for (int i = 1; i < len - 1; i++) {
	        g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
	    }
	    return g;
	}
	
	public static long lcm_n(long[] numbers) {
		long l;
		l = numbers[0];
		for (int i = 1; i < numbers.length; i++) {
			l = lcm(l, numbers[i]);
		}
		return l;
	}
	public static int H,W;
	public static char[][] c;
	public static boolean[][] b;
	
	

    
	
	
 public static void main(String[] args) {
	 
	 Scanner sc=new Scanner(System.in);
	 int N=sc.nextInt(),M=sc.nextInt();
	 
	 long[] A=new long[N];
	 
	 Map<Long,Integer> map = new TreeMap<Long,Integer>(Collections.reverseOrder());
	 
	 long sum = 0;
	 
	 for(int i=0;i<N;i++) {
		 A[i]=sc.nextLong();
		 
	 }
	 
	 Arrays.sort(A);
	 
	 for(int i=0;i<M;i++) {
		 int B=sc.nextInt();
		 long C=sc.nextLong();
		 
		 if(map.containsKey(C)) {
			 map.put(C,map.get(C)+B);
		 }else {
			 map.put(C,B);
		 }
	 }
	 
	 Iterator<Long> keyitr = map.keySet().iterator();
	 long value=0,key = 0;
	 for(int i=0;i<N;i++) {
		 if(value==0&&keyitr.hasNext()) {
			 key=keyitr.next();
			 value=map.get(key);
		 }else if(value==0&&!keyitr.hasNext()) {
			 key=0;
			 value = 0;
		 }
		 if(A[i]<key) {
			 sum+=key;
			 value--;
		 }else {
			 sum+=A[i];
		 }
		 
	 }
		 
	 
	 System.out.println(sum);
	
}
 
 
}

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;
char maze[10][10];



int main(){

    int h,w;
    cin>>h>>w;
    
    int cnt=0;
    rep(i,h)rep(k,w){cin>>maze[i][k];
    if(maze[i][k]=='#')cnt++;
    }
    
    queue<int>q;
    int dx[2]={0,1};
    int dy[2]={1,0};

    q.push(0);
    q.push(0);
    bool ans=(cnt ==h+w-1);

    while(!q.empty()){
    
        int nowx=q.front();q.pop();
        int nowy=q.front();q.pop();

        if(nowx==w-1 && nowy==h-1)break;

        int cnt2=0;

        rep(i,2){
            int nx=nowx+dx[i];
            int ny=nowy+dy[i];

            if(nx>=w||ny>=h)continue;

            if(maze[ny][nx]=='#'){
            cnt2++;
            q.push(nx);
            q.push(ny);
            }
        }

        if(cnt2!=1){
        ans=false;
        break;
        }
    }

    
    
    
    if(ans){
        cout<<"Possible"<<endl;
    }
    else{
        cout<<"Impossible"<<endl;
    }

    return 0;

}
/*
2 2
.#
.#

4 5
#....
##...
.#...
.####

4 5
##..#
.##..
..#..
..###
*/


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int mod = 1000000007;
const int N = 100005;
#define ll long long 
ll q_mod(ll a,ll b){
	ll tmp = 1;
	a = a%mod;
	while (b){
		if (b&1) tmp = tmp * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return tmp;
}
int x[N];
int a[N];
int main(){
	int n;
	cin>>n;
	int flag = 0;
	for (int i = 0; i < n; ++i){
		cin>>x[i];
		if (x[i] == 0 && n % 2 != 0) flag++;
		else if (x[i] == 0 && n%2 == 0) flag = 2;
		a[x[i]]++;	
	}
	for (int i = 0; i < n; ++i){
		if (x[i]!=0 && a[x[i]]!=2) flag = 2;
	}
	if (flag > 1) printf("0\n");
	else{
		ll t = n/2;
		ll ans = q_mod(2,t);
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define Int long long
using namespace std;

const int MAXN=500005;
const int NAX=1005;
const long long  MOD=(long long)(998244353);

Int N,M,K;
Int X,Y,Z;
Int H,W;
Int perform(Int x){
    return (x*(x+1))/2LL;
}
vector<Int> A;
vector<int> adj[MAXN];
using D=long double;

bool inRange(Int a,Int b){
    return a*b<=0;
}

long long C[NAX][NAX];
const D pi=3.14159265359;


long long ModExpo(long long x,unsigned long long y,long long M){
    Int ans=1;
    ans=(long long)ans;
    
    while(y>0){
        if(y&1) ans=((ans%M)*(x%M))%M;
        y>>=1LL;
        x=((x%M)*(x%M))%M;
    }
    return ans%M;
}
long long fac[MAXN];
void fillFac(){
    fac[0]=1;
    for(int i=1;i<MAXN;++i){
        fac[i]=((fac[i-1]%MOD)*(i%MOD))%MOD;
    }
}

long long ModInv(long long x){
    return ModExpo(x,MOD-2,MOD);
}

long long FermatLast(long long n,long long r){
    if(r>n) return 0;
    if(!r) return 1;
    return (fac[n] * ModInv(fac[r]) % MOD * ModInv(fac[n - r]) % MOD) % MOD;
}

Int performMod(Int x){
    Int y=((x%MOD)*((x+1)%MOD))%MOD;
    return (y*ModInv(2))%MOD;
}

Int madd(Int x,Int y){
    return (x+y)%MOD;
}

Int mmul(Int x,Int y){
    return ((x%MOD)*(y%MOD))%MOD;
}


bool isMSB(int bit,Int x){
    return (int)(floor(log2l(x)))==bit;
}
bool VIS[MAXN];
void dfs(int u){
    VIS[u]=true;
        for(auto &v:adj[u]){
            if(!VIS[v]){
                dfs(v);
            }
        }
}
int main()
{
    string S="ACL";
    cin>>K;
    while(K--) cout<<S;
    cout<<"\n";
}


Measured memory_bytes: 15336
// Problem: D - Redistribution
// Contest: AtCoder - AtCoder Beginner Contest 178
// URL: https://atcoder.jp/contests/abc178/tasks/abc178_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define ll long long int
#define ii int
#define du double
#define jmp "\n"
#define vl vector<ll>
#define vvl vector<vl>
#define pb push_back
#define printv(v)     \
  for (auto x : v)    \
    cout << x << " "; \
  cout << jmp;
#define vi vector<int>
#define vb vector<bool>
#define ump unordered_map
#define SORT(v) sort(v.begin(), v.end())
#define REV(x) reverse(x.begin(), x.end())
#define all(x) x.begin(), x.end()
#define SET(x, a) memset(x, a, sizeof(x))
#define si(x) x.size()
#define ff first
#define ss second
#define iin insert
#define deb(x) cout << "test " << #x << "=" << x << jmp
#define deb2(x, y) cout << "test " << #x << "=" << x << "," << #y << "=" << y << jmp
using namespace std;
const ll nax = 1e9 + 7;
void solve()
{
  ll n;
  cin >> n;
  ll dp[n + 1];
  SET(dp, 0);
  if (n >= 3 && n <= 5)
  {
    cout << 1;
    return;
  }
  if (n < 3)
  {
    cout << 0;
    return;
  }
  for (ll i = 0; i < 3; i++)
    dp[i] = 0;
  for (ll i = 3; i <= n; i++)
    dp[i] = 1;
  for (ll i = 4; i <= n; i++)
  {
    for (ll j = 3; j <= n; j++)
      if (i - j >= 3)
        dp[i] = ((dp[i] + dp[i - j])) % nax;
  }
 
  cout << dp[n] << jmp;
}
int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll t = 1;
  //cin >> t;
  while (t--)
    solve();
  return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<string>
#include<vector>

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

template<class T> void swap(T &a, T &b ){
    T temp;
    temp = a;
    a = b;
    b = temp;   
}

int main(){
    vector<int> X;
    int x;
    ULL sum;
    int N, M;
    int i;

    cin >> N >> M;
    for(i=0;i<N;i++){
        cin >> x;
        X.push_back(x);
    }
    sort(X.begin(),X.end());
    for(i=0;i<M;i++){
        X[N-1] /= 2;
        if( N > 1 && X[N-1] < X[N-2]){
            /*
            for(int j=0; j<N;j++){
                cout << X[j] << " ";
            }
            cout << endl;*/
            x = X[N-1];
            X.pop_back();
            auto itr = lower_bound(X.begin(),X.end(),x);
            X.insert(itr,x);
            /*
            for(int j=0; j<N;j++){
                cout << X[j] << " ";
            } 
            cout << endl;
            */
        }
    }
    sum = 0;
    for(i=0;i<N;i++){
        sum = sum + X[i];
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 892
n=int(input())
s=int(input())
r=int(n**0.5)
for b in range(2,r+2):
  m=n
  t=0
  while m:
    t+=m%b
    m//=b
  if t==s:
    print(b)
    exit()
for p in range(1,r)[::-1]:
  q=s-p
  b=1+(n-s)//p
  if 1<=p<b and 0<=q<b and (n-s)%p==0:
    print(b)
    exit()
if n==s:
  print(n+1)
  exit()
print(-1)

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

using namespace std;
#define int long long
typedef long long ll;

std::vector<std::string> split(const std::string &str, char sep)
{
    std::vector<std::string> v;
    std::stringstream ss(str);
    std::string buffer;
    while( std::getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

signed main() {
    string str;
    cin >> str;
    int price = 700;
    for (auto c : str) price += c == 'o' ? 100 : 0;
    cout << price << endl;
}



Measured memory_bytes: 256
import java.io.*;
public class Main {
    public static void main(String[] args) {
      try{BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
      String line = reader.readLine();
      int x = Integer.parseInt(line);


      System.out.println(x*x*x);}catch(IOException e){
          System.out.println(e);
      }catch(NumberFormatException e){
          System.out.println("e");
      }
}
}


Measured memory_bytes: 24312
#include <cstdio>
#include <iostream>
#include <string.h>

#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)

using namespace std;

int main() {
	int n;
	int base = 0, out = 0, score = 0;
	cin >> n;  
    while(1) {
        char str[10];
        if(EOF == scanf("%s", str)) break;
        if(!strcmp(str, "OUT")) {
            out++;
            if(out >= 3) {
                cout << score <<endl;
                score = out = base = 0;
                n--;
            }
        } else if(!strcmp(str, "HOMERUN")) {
            score += base + 1;
            base = 0;
        } else {
            base++;
            if(base >= 4) {
                score++;
                base--;
            }
        }
    }
    if(n) {
        cout << score << endl;
    }
	return 0;
}

Measured memory_bytes: 1192
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  int r0, w0, c, r;
  while (cin >> r0 >> w0 >> c >> r, r0)
  {
    int t = r0 / w0, x;
    for (x = 1; t < c; ++x)
    {
      t = (r0 + x * r) / w0;
    }
    cout << x - 1 << endl;
  }

  return 0;
}



Measured memory_bytes: 3096
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var h = int.Parse(line[0]);
        var w = int.Parse(line[1]);
        var map = new int[h, w];
        for (int i = 0; i < h; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            for (int j = 0; j < w; j++) map[i, j] = int.Parse(line[j]);
        }
        var ret = 999999999;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
            {
                var t = getAns(map, i, j, h, w);
                ret = Math.Min(ret, t);
            }
        Console.WriteLine(ret);
    }
    public static int getAns(int[,] map, int a, int b, int h, int w)
    {
        var ret = 0;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                {
                    var ta = Math.Abs(i - a);
                    var tb = Math.Abs(j - b);
                    ret += Math.Min(ta, tb) * map[i, j];
                }
        return ret;
    }
}



Measured memory_bytes: 9216
// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, ai[MAX_N], fac[MAX_N];
char str[MAX_N];

int binomial(int n_, int k_) { return fac[n_] - fac[k_] - fac[n_ - k_]; }

int main()
{
    scanf("%d%s", &n, str + 1);
    bool flag = false;
    for (int i = 1; i <= n; i++)
        ai[i] = str[i] - '1', flag |= (ai[i] == 1);
    for (int i = 1; i <= n; i++)
    {
        int acc = i;
        while (!(acc & 1))
            fac[i]++, acc >>= 1;
        fac[i] += fac[i - 1];
    }
    if (!flag)
        for (int i = 1; i <= n; i++)
            ai[i] >>= 1;
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if ((ai[i] & 1) && (!binomial(n - 1, i - 1)))
            ans ^= 1;
    if (!flag)
        ans <<= 1;
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 12620