akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool neg=c=='-';
	neg?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return neg?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
template<class T>inline void mset(T a,int v,int n){memset(a,v,n*sizeof(a[0]));}
const int N=20;
int anslen=0;
bool stk[N+2];
int ss=0;
namespace T{
	const int N=1<<23;
	int f[N];
	inline void init(const int n){
		mset(f,0,1<<(n+1));
	}
	inline void ins(int s,int i){
		for(int x=1;;x=(x<<1)|((s>>--i)&1)){
			++f[x];
			if(i==0)break;
		}
	}
	int tmp_f[N];
	void dfs_store(const int x){
		tmp_f[x]=f[x];
		if(f[x]==0)return;
		dfs_store(x<<1);
		dfs_store((x<<1)|1);
	}
	void dfs_mg(const int x,const int v){
		if(tmp_f[v]==0)return;
		f[x]+=tmp_f[v];
		dfs_mg(x<<1,v<<1);
		dfs_mg((x<<1)|1,(v<<1)|1);
	}
	void solve(const int x){
		if(f[x]==0)return;
		const int lson=x<<1,rson=lson|1;
		solve(lson),solve(rson);
		dfs_store((lson<<1)|1),dfs_store(rson<<1);
		dfs_mg(lson,rson<<1),dfs_mg(rson,(lson<<1)|1);
	}
	void findans(const int x,const int dep,const int k){
		if(f[x]<k)return;
		apmax(anslen,dep);
		findans(x<<1,dep+1,k);
		findans((x<<1)|1,dep+1,k);
	}
	bool putans(const int x,const int k){
		if(f[x]<k)return false;
		if(ss==anslen)return true;
		ss++;
		stk[ss]=0;
		if(putans(x<<1,k))return true;
		stk[ss]=1;
		if(putans((x<<1)|1,k))return true;
		ss--;
		return false;
	}
}
int main(){
	const int n=ni;
	T::init(n);
	const int k=ni;
	for(int i=0;i<=n;i++){
		static char str[(1<<N)+10];
		scanf("%s",str);
		for(int s=0,ts=1<<i;s<ts;s++){
			if(str[s]=='1'){
				T::ins(s,i);
			}
		}
	}
	T::solve(1);
	T::findans(1,0,k);
	T::putans(1,k);
	for(int i=1;i<=ss;i++){
		putchar('0'+stk[i]);
	}
	putchar('\n');
	return 0;
}


Measured memory_bytes: 44288
def bowling(game):
	game=map(int,game.split())
	score,thrw=0,1
	for flame in range(10):
		if game[thrw]==10:
			score+=sum(game[thrw:thrw+3])
			thrw+=1
		elif game[thrw]+game[thrw+1]==10:
			score+=10+game[thrw+2]
			thrw+=2
		else:
			score+=sum(game[thrw:thrw+2])
			thrw+=2
	return game[0],score
	
while 1:
	n=input()
	if n==0:break
	ls=[bowling(raw_input()) for i in range(n)]
	for k,s in sorted(sorted(ls),key=lambda x:x[1],reverse=1):
		print k,s

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

struct edge {
    int to, cost;
};
class dijkstra {
    int V;
    int d[100002];
    priority_queue<P, vector<P>, greater<P>> que;
    void update(int s, vector<edge> G[]) {
        fill(d, d + V + 1, 100000000000ll);
        d[s] = 0;
        que.push(make_pair(0, s));
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (d[v] < p.first) continue;
            rep(i, G[v].size()) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(make_pair(d[e.to], e.to));
                }
            }
        }
    }

public:
    dijkstra(int v, int s, vector<edge> G[]) {
        V = v;
        update(s, G);
    }
    int find(int e) {
        return d[e];
    }
};
int gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
bool prime(int a) {
    if (a == 1) return false;
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}
class Union_Find {
private:
    vector<int> t, s;

public:
    Union_Find(int max_length) {
        rep(i, max_length + 1) {
            t.push_back(i);
            s.push_back(1);
        }
    }
    void Union(int x, int y) {
        if (same(x, y)) return;
        int tx = Find(x), ty = Find(y);
        if (s[tx] < s[ty]) {
            s[ty] += s[tx];
            t[tx] = ty;
        }
        else if (s[tx] > s[ty]) {
            s[tx] += s[ty];
            t[ty] = tx;
        }
        else if (tx > ty) {
            t[tx] = ty;
            s[ty] += s[tx];
        }
        else {
            t[ty] = tx;
            s[tx] += s[ty];
        }
    }
    int Find(int n) {
        if (t[n] == n)
            return n;
        else
            return t[n] = Find(t[n]);
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int get_Size(int a) {
        return s[a];
    }
};
signed main() {
    int n,a,b,c,d;
    string s;
    cin>>n>>a>>b>>c>>d>>s;
    bool bo=false,boo=false;
    REP(i,2,s.size()){
        if(((a<i&&i<c)||(b<i&&i<d))&&s[i]=='#'&&s[i-1]=='#')boo=true;
        if(d>=i&&a<=i&&b<=i&&s[i]=='.'&&s[i-1]=='.'&&s[i-2]=='.')bo=true;
    }
    if((bo==false&&d<c)||boo)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll mo = 998244353;
const int M = 100+50;
struct yen{
	long long a,b;
};
bool cmp(yen a,yen b){
	return a.a<b.a;
}
unsigned long long ans=0;
int main(){
	int n,m;
	cin>>n>>m;
	yen p[n+5];
	for(int i=0;i<n;i++)
		cin>>p[i].a>>p[i].b;
	sort(p,p+n,cmp);
	for(int i=0;i<n;i++){
		if(p[i].b<=m){
			ans+=p[i].a*p[i].b;
			m-=p[i].b;
		}
		else{
			ans+=p[i].a*m;
			break;
		}
	}
	cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 1792
package main

import "fmt"

type money struct {
	amount float64
	isJPY  bool
}

func main() {
	var N int
	fmt.Scan(&N)
	otd := make([]money, N)
	for i := range otd {
		var s string
		fmt.Scan(&otd[i].amount)
		fmt.Scan(&s)
		if s == "JPY" {
			otd[i].isJPY = true
		}
	}
	sum := 0.0
	for i := range otd {
		if otd[i].isJPY {
			sum += otd[i].amount
		} else {
			sum += otd[i].amount * 380000.0
		}
	}
	fmt.Printf("%v\n", sum)
}


Measured memory_bytes: 512
use proconio::input;

fn main() {
    input! {
        n: usize,
        t_l: i64,
        t: [i64; n],
    };
    let mut s = 0;
    let mut l = 0;
    let mut r = t_l;
    for &t_i in t.iter() {
        if t_i <= r {
            r = t_i + t_l;
        } else {
            s += r - l;
            l = t_i;
            r = t_i + t_l;
        }
    }
    s += r - l;
    let ans = s;
    println!("{}", ans);
}


Measured memory_bytes: 5400
# -*- Coding: utf-8 -*-
INF = 1001001001
n, m = map(int, input().split())

def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[j]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    

to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
if len(to) == 0:
  print(-1)
else:  
  c = [bfs(i, to) for i in range(n)]
  ans = [1 for i in range(n+1)]
  for i in range(n):
    if len(ans) > len(c[i]):
      ans = c[i]
  if len(ans) == n + 1:
    print(-1)
  else:
    print(len(ans))
    for v in ans[::-1]:
      print(v+1)
    

Measured memory_bytes: 58584
class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)
  def initialize
    @n = gets.to_s.to_i
    @a = gets.split.map(&:to_i)
    @ans = []
  end

  def base
    minv = a.min
    mini = a.index(minv)
    maxv = a.max
    maxi = a.index(maxv)
    if minv.abs < maxv.abs
      return maxi, maxv
    else
      return mini, minv
    end
  end

  def add(x,y)
    @ans << [x+1,y+1].join(" ")
    a[y] += a[x]
  end

  def solve
    i, v = base
    n.times do |j|
      next if i == j
      add(i,j)
    end

    if v < 0
      (n-1).downto(1) do |i|
        add(i,i-1)
      end
    else
      0.upto(n-2) do |i|
        add(i,i+1)
      end
    end
    @ans
  end

  def show(ans)
    puts ans.size
    ans.each do |s|
      puts s
    end
  end
end

Problem.new.instance_eval do
  show(solve)
end

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

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

    if(S.size() <= K){
      cout << S << endl;
    }
    else{
      for(int i= 0; i<K; i++){
         cout << S.at(i);
      }
      cout << "..." << endl;
    }
}

Measured memory_bytes: 3628
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define repd(i, n) for (ll i = (n)-1; i >= 0; --i)
#define INF 10e12
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    long double area = W * H / double(2);
    int cut = 0;
    if (x == W / double(2) && y == H / double(2))
        cut = 1;
    cout << fixed << setprecision(15);
    cout << area << " " << cut << endl;
}

Measured memory_bytes: 256
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

long mod = 10^^9 + 7;
//long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { x.modm(y.modpow(mod - 2)); }

void main()
{
	auto X = RD;

	long a = 100;
	long ans;
	foreach (i; 1..10^^7)
	{
		a += a / 100;
		if (a >= X)
		{
			ans = i;
			break;
		}
	}

	writeln(ans);
	stdout.flush;
	debug readln;
}

Measured memory_bytes: 2744
#include <iostream>

using namespace std;
int main()
{
	long long k,a,b,x;
	long long ans=0;
	cin >> k >> a >> b;
	if (a+1 >= b)ans = 1 + k;
	else {
		x = k - a + 1 - ((k - a + 1) % 2);
		//cout << "b-a  " << b - a << endl;
		//cout << "x/2  " << x/2 << endl;
		ans = 1 + k - x + ((b - a)*x) / 2;
	}
	 cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	LL n, a, b;
	cin >> n >> a >> b;
	if((b - a) % 2 == 0) cout << ((b - a) / 2) << endl;
	else cout << min((a + b - 1) / 2, (n - a + 1 + n - b + 1 - 1) / 2) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a%b, y, x);
	y -= a / b * x;
	return d;
}

bool check(llint a, llint b) {
	return a > b;
}

int main() {
	string s;
	cin >> s;
	llint ans = 0;
	int tmp = 0;
	rep(i, s.size() - 1) {
		if (s[i + 1] != '9') {
			tmp = 1;
			break;
		}
	}
	if (tmp == 0) {
		ans += (llint)(s[0] - '0');
		ans += 9 * (llint)(s.size() - 1);
	}
	else {
		ans += (llint)((s[0] - '0') - 1);
		ans += 9 * (llint)(s.size() - 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table
N = input()
ans = 1
nlist = [0]*1000
for i in xrange(1,N+1):
    for j in prime_decomposition(i):
        nlist[j-1] += 1

for j in nlist:
    ans *= (j+1)

print ans%1000000007

Measured memory_bytes: 2692
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
   string s , t ; 
   cin>>s>>t ; 
   int cnt=0 ;
   for(int i =0;i<s.size();i++){
           if(s[i]!=t[i])cnt++;
   }cout<<cnt;
}


Measured memory_bytes: 3760
import java.util.*;
import java.io.*;

 public class Main{
// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}

//......................................@uthor_Alx..............................................
   public static void main(String[] args) throws  IOException{
	        		  assign();
	        		  	int n=int_v(read());
	        		  	int[] arr=int_arr();
	        		  	int x=0;
	        		  	for(int z:arr){x^=z;}
	        		  	int[] res=new int[n];
	        		  	for(int i=0;i<n;i++){
	        		  		for(int j=0;j<32;j++){
	        		  			int b=arr[i]&1<<j;
	        		  			int xb=x&1<<j;
	        		  			if((b==0&&xb!=0)||(b!=0&&xb==0)){
	        		  				res[i]+=1<<j;
	        		  			}
	        		  		}
	        		  	}
	        		  	for(int i:res){out.write(i+" ");}

	        		  	//out.write(res+"");
                      	out.flush();
	        		 
	}
}
	       

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> array(n);
  for(int i = 0; i < n; i++){
    cin >> array.at(i);
  }
  sort(array.begin(),array.end(),greater<int>());
  int sum = 0;
  for(int i = 0; i < k; i++){
    sum += array.at(i);
  }
  cout << sum << endl;
}

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

using namespace std;
int h[100005];
int dp[100005];
int main(){
	int n,k;
    cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
    for(int i=0;i<n;i++)dp[i]=1e9;
	dp[0]=0;
	for(int i=1;i<n;i++){
		for(int j=1;j<=k;j++){
			if(i>=j){
				dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
			}
		}
	}
    cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <time.h>
#include <iomanip>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::vector<ll> VI;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define SZ(x) ((int)((x).size()))
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
int main()
{
    ll a, b, n;
    read(a), read(b), read(n);
    if (b > n)
    {
        printf("%lld\n", n * a / b);
    }else
    {
        printf("%lld\n", (b - 1) * a / b);
    }
    
}

Measured memory_bytes: 3692
fn solve() {
    let stdin = std::io::stdin();
    let mut scn = Scanner { stdin: stdin.lock() };
    let mut x: u64 = scn.read();
    let mut result = 0;
    result += x / 500 * 1000;
    x %= 500;
    result += x / 5 * 5;
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}
pub mod utils {
    const DYX: [(isize, isize); 8] = [
        (0, 1),   //right
        (1, 0),   //down
        (0, -1),  //left
        (-1, 0),  //top
        (1, 1),   //down right
        (-1, 1),  //top right
        (1, -1),  //down left
        (-1, -1), //top left
    ];

    pub fn try_adj(y: usize, x: usize, dir: usize, h: usize, w: usize) -> Option<(usize, usize)> {
        let ny = y as isize + DYX[dir].0;
        let nx = x as isize + DYX[dir].1;
        if ny >= 0 && nx >= 0 {
            let ny = ny as usize;
            let nx = nx as usize;
            if ny < h && nx < w {
                Some((ny, nx))
            } else {
                None
            }
        } else {
            None
        }
    }
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8572
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SLR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, A = LI()
    X = LI()
    Y = [xi - A for xi in X]
    z = max(A, max(X))

    dp = make_list(N+1, 2*z*N+1)
    dp[0][z*N] = 1

    for i in range(1, N+1):
        for s in range(2*z*N+1):
            if 0 <= s - Y[i-1] <= 2*z*N:
                dp[i][s] = dp[i-1][s] + dp[i-1][s - Y[i-1]]
            else:
                dp[i][s] = dp[i-1][s]

    print(dp[-1][z*N]-1)


if __name__ == '__main__':
    main()

Measured memory_bytes: 73948
def main():
    import bisect
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    a_sum,b_sum = [0], [0]
    for i in range(n):
        a_sum.append(a_sum[i]+a[i])
    for i in range(m):
        b_sum.append(b_sum[i]+b[i])
    ans = 0
    for i in range(n+1):
        cst = a_sum[i]
        if cst > k:
            break
        cst = k-cst
        j = bisect.bisect_right(b_sum,cst)
        if i+j-1>ans:
            ans = i+j-1
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 47516
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int INF = 330000;
int n, m, s, t, ans;
vector<int> edge[330000];
int dist[330000];


void dijkstra(int u) {
  priority_queue<P, vector<P>, greater<P> > pq;
  
  for (int i = 0; i < n * 3; i++) {
    dist[i] = INF;
  }
  
  dist[u] = 0;
  pq.push(P(0, u));
  
  while (pq.size()) {
    P p = pq.top();
    pq.pop();
    u = p.second;
    if (dist[u] < p.first) continue;
    for (int v: edge[u]) {
      if (dist[v] > dist[u] + 1) {
        dist[v] = dist[u] + 1;
        pq.push(P(dist[v], v));
      }
    }
  }
}

int main() {
  cin >> n >> m;
  
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edge[u].push_back(v+n);
    edge[u+n].push_back(v+2*n);
    edge[u+2*n].push_back(v);
  }
  
  cin >> s >> t;
  s--;
  t--;
  
  dijkstra(s);
  
  if (dist[t] == INF) {
    ans = -1;
  } else {
    ans = dist[t] / 3;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 18560
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define N 3005
ll inf = 1e14;
ll mod = 1e9 + 7;
char en = '\n';

ll abs1(ll x) {
  if (x < 0)
    return -x;
  return x;
}
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}

ll dp[N][N][2];
ll arr[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n, k;
  cin >> n;
  for (ll i = 1; i <= n; i++)
    cin >> arr[i];

  memset(dp, 0, sizeof(dp));

  for (ll i = 1; i <= n; i++) {
    dp[i][i][0] = arr[i];
    dp[i][i][1] = -arr[i];
  }

  for (ll len1 = 2; len1 <= n; len1++) {
    for (ll i = 1; i <= n - len1 + 1; i++) {
      ll j = i + len1 - 1;
      dp[i][j][0] = max(arr[i] + dp[i + 1][j][1], arr[j] + dp[i][j - 1][1]);
      dp[i][j][1] = min(-arr[i] + dp[i + 1][j][0], -arr[j] + dp[i][j - 1][0]);
    }
  }

  cout << dp[1][n][0] << en;

  return 0;
}


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

int main() {
    int n, a[105];
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i]; 
	for(int j = n; j > 1; j--)
		cout << a[j] << " ";
	cout << a[1];	
    cout << endl;
    return 0;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define mod 1000000007

const long double PI = acos(-1);
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

int main(){
    ll n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    int index = 1;
    int ans = 0;
    for (int i = 0; i < n; i++){
        if(a[i] != index) ans++;
        else index++;
    }
    index--;
    if(index) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define loop(i, a, b) for(ll i = a; i < b; i++)
#define rloop(i, e, s) for(ll i = e; i >= s; i--)
#define mod 1000000007
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr);

int main()
{
    ll n, ans = 0;
    cin >> n;
    ll b[n-1];
    loop(i, 0, n-1) cin >> b[i];
    ans += b[n-2];
    rloop(i, n-2, 0){
        if(i == 0){
            ans += b[i];
            break;
        }
        ans += min(b[i], b[i-1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#define ll long long

using namespace std;

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    
    ll mx = max(a*c, a*d), my = max(b*c, b*d);
    cout << max(mx, my) << endl;
    
    return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main() {
    int a,b,c,d,e;
    scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
    if(a == 0) {
        printf("1");
    } else if(b == 0) {
        printf("2");
    } else if(c == 0) {
        printf("3");
    } else if(d == 0) {
        printf("4");
    } else if(e == 0) {
        printf("5");
    }
}

Measured memory_bytes: 1584
# coding: utf-8
# Your code here!

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

L = list(map(int,input().split()))

#print(L)
print
count = 1

bouns = 0
for i in range(N):
    bouns += int(L[i])
   # print (bouns)
    if bouns <= X :
        count+=1
      #  print("!!")
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

const string YES = "Yes";
const string NO = "No";

void solve(long long N, std::vector<long long> A, std::vector<long long> B){
    vector<pair<long long, long long>> tasks(N);
    for(int i=0; i<N; i++)tasks[i]=make_pair(B[i], A[i]);
    sort(tasks.begin(), tasks.end());

    auto time = 0ll;
    for(auto kv: tasks){
        time += kv.second;
        if(time > kv.first){
            cout << NO << endl;
            return;
        }
    }

    cout << YES << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int mod_pow(long long x, long long n, long long _mod){
  long long ret = 1;
  while(0 < n){
    if((n % 2) == 0){
      x = (x * x) % mod;
      n >>= 1;
    } else {
      ret = (ret * x) % _mod;
      --n;
    }
  }
  return ret;
}

int main(){
  int N, A;
  map<int, int> mp;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A;
    mp[A]++;
  }
  int start = (N % 2 == 0 ? 1 : 0);
  if(start == 0){
    if(mp[start] != 1){
      cout << 0 << endl;
      return 0;
    }
    start += 2;
  }
  
  for(int i = 0; i < N / 2; i++){
    if(mp[start] != 2){
      cout << 0 << endl;
      return 0;
    }
    start += 2;
  }

  cout << mod_pow(2, N / 2, mod) << endl;
  return 0;
}


Measured memory_bytes: 3200
W, H, n = map(int, input().split())
l = [[True]*W]*H
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        for h in range(H):
            for w in range(x):
                l[h][w] = False
    elif a == 2:
        for h in range(H):
            for w in range(x, W):
                l[h][w] = False
    elif a == 3:
        for h in range(y):
            l[h] = [False]*W
    else:
        for h in range(y, H):
            l[h] = [False]*W

ans = 0
for i in range(H):
    for j in range(W):
        if l[i][j]:
            ans += 1
print(ans)

Measured memory_bytes: 68588
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int a[]=new int[N];
		for(int i=0;i<N;i++) {
			a[i]=sc.nextInt();
		}
		Arrays.sort(a);
		
		System.out.println(a[N-1]-a[0]);
	}
}


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

using namespace std;


int main() {
	long n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		v[i] -= (i + 1);
	}

	sort(v.begin(), v.end());
	long d = n / 2;
	vector<int> midL = { d - 1, d ,d + 1 };

	long mn = -1;
	for (auto mid : midL) {
		long sum = 0;
		for (auto x : v) {
			sum += abs(x - v[mid]);
		}
		if (mn < 0) { mn = sum; } else { mn = min(sum, mn); }
	}
	cout << mn << endl;

}

Measured memory_bytes: 1024
N = int(input())
if N == 1:
    print(1)
    exit()
ans = 0
max_tmp = 0
for i in range(1,N+1):
    t = i
    tmp = 0
    while True:
        if t % 2 == 1:
            break
        t /= 2
        tmp += 1
    if max_tmp < tmp:
        ans = i
        max_tmp = tmp
print(ans)

Measured memory_bytes: 3188
#include <stdio.h>

int main(void)
{
	int S;
	int h, m, s;
	
	scanf("%d", &S);
	
	s = S % 60;
	m = ((S - s) / 60) % 60;
	h = (((S - s) / 60) - m) / 60;
	
	printf("%d:%d:%d\n", h, m, s);
	
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
typedef pair<int, int> P;
map<P, int> mp;
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w, n;
    cin >> h >> w >> n;
    int a[100010], b[100010];
    rep(i, n) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        rep(k, 9) {
            int x = a[i] + k % 3 - 1;
            int y = b[i] + k / 3 - 1;
            mp[{x, y}]++;
        }
    }
    int ans[10] = {};
    ans[0] = (h - 2) * (w - 2);
    for(auto itr = mp.begin(); itr != mp.end(); itr++) {
        int x = itr->first.first;
        int y = itr->first.second;
        if(x <= 0 || x >= h - 1 || y <= 0 || y >= w - 1) continue;
        int c = itr->second;
        if(c != 0) {ans[c]++; ans[0]--;}
    }
    // rep(i, n) {
    //     rep(k, 9) {
    //         int x = a[i] + k % 3 - 1;
    //         int y = b[i] + k / 3 - 1;
    //         if(x <= 0 || x >= h - 1 || y <= 0 || y >= w - 1) continue;
    //         int c = mp[{x, y}];
    //         if(c != 0) {ans[c]++; ans[0]--;}
    //     }
    // }
    rep(i, 10) cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 58112
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
d = {}
for i in range(n):
    for j in range(i+1, n):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        if q < 0:
            p, q = -p, -q
        if q == 0:
            p = abs(p)
        d.setdefault((p, q), 0)
        d[(p, q)] += 1
m = 0
pair = (0, 0)
for x in d:
    if d.get(x, 0) > m:
        m = d.get(x, 0)
        pair = x
        
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for _ in range(n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    def size(self, x):
        return self.par[self.find(x)]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.size(x) < self.size(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return 1

uf = UnionFind(n)
ans = n
for i in range(n):
    for j in range(i+1, n):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        if q < 0:
            p, q = -p, -q
        if q == 0:
            p = abs(p)
        if (p, q) == pair:
            ans -= uf.unite(i, j)
print(ans)

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N,M;
  cin>>N>>M;
  vector<int>x(M),y(M);
  for(int i=0;i<M;i++)cin>>x[i]>>y[i];
  vector<vector<int>>G(N);
  for(int i=0;i<M;i++){
    x[i]--,y[i]--;
    G[x[i]].push_back(y[i]);
  }
  vector<bool>used(N,false);

  vector<int>newG;
  auto Y=[](auto f){
    return [=](auto&&... args){
      return f(f,forward<decltype(args)>(args)...);
    };
  };
  auto dfs=[&](auto f,auto n)->decltype(void()){
    used[n]=true;
    for(auto it:G[n]){
      if(used[it])continue;
      f(f,it);
    }
    newG.push_back(n);
    return;
  };
  for(int i=0;i<N;i++){
    if(!used[i])Y(dfs)(i);
  }
  reverse(rng(newG));

  vector<int>dp(N,0);
  dp[0]=0;
  for(int i=0;i<N;i++){
    for(auto it:G[newG[i]]){
      dp[it]=max(dp[it],dp[newG[i]]+1);
    }
  }
  int ans=0;
  for(auto it:dp)ans=max(ans,it);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 8824
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
#define PI acos(-1)
#define oo LLONG_MAX
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*
3 4
2 2 4

DPかMapか

DP
0 1 4+1 3
      うつして、0を2倍して、DP+A[i]加算して、DPたす
      今とるとき、2^i倍してとる
      0を2倍して、A[i]を加算して、DPの0以外を加算
  0 1 2     3     4 5
0 1 1 2 0 2 4 4 4
1 0 0 0   0
2 0 1 1 2 4 4 4 8 3 6
3 0 0 0   0
4 0 0 0 1 1 1 5 6
5 

14
0 1 2 3
1 1 2 4 
0 0 0 0 
0 1 4 8 
0 0 0 0 
0 1 5 14 


3
1 1 2 4 
0 0 0 0 
0 1 2 2 
0 0 0 0 
0 0 1 3 

7
1 1 2 4 
0 0 0 0 
0 1 3 3 
0 0 0 0 
0 0 3 7 


2 2　と 4
{2,2} {

3をつくるとき。

1,1,1,2

{1,1,1} = 2通り =2^1
{1,2} = 4通り = 4要素のうち2つつかって2つあまってるから2^2

1,1,1,2,5

{1,1,1,5} = 4通り
{1,2,5} = 8通り

*/
ll MOD = 998244353;
vector<vector<ll>> DP(3010, vector<ll>(3010, 0));

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  ll N, S; cin >> N >> S;
  DP[0][0] = 1;
  DP[1][0] = 1;
  for(ll i=2; i<=N; i++)
    (DP[i][0] = DP[i-1][0] * 2) %= MOD;
  for(ll i=1; i <= N; i++){
    ll A; cin >> A;
    //まずコピー
    for(ll j = 1; j < 3001; j++)
      (DP[i][j] += DP[i-1][j]) %= MOD;
    //A加算
    for(ll j = 3001 - A; j >= 0; j--)
      (DP[i][j + A] += DP[i][j]) %= MOD;
    //1個前加算
    for(ll j = 1; j < 3001; j++)
      (DP[i][j] += DP[i-1][j]) %= MOD;
  }
  cout << DP[N][S] <<endl;  

/*rep(j, S+1){
  rep(i, N+1)
    cout<<DP[i][j]<<" ";
  cout<<endl;
}*/
}


Measured memory_bytes: 74548
#include<bits/stdc++.h>
const int N=100007,inf=0x3f3f3f;
struct edge{
	int to,v,nx;
}e[N];
int e0[N],e1[N],h[N],q[N],ep=2,S,T;
bool bfs(){
	for(int i=1;i<=T;++i)h[i]=0,e1[i]=e0[i];
	int ql=0,qr=0;
	h[q[++qr]=S]=1;
	while(ql!=qr){
		int w=q[++ql];
		if(w==T)return 1;
		for(int i=e0[w];i;i=e[i].nx)if(e[i].v){
			int u=e[i].to;
			if(!h[u])h[q[++qr]=u]=h[w]+1;
		}
	}
	return 0;
}
int min(int a,int b){return a<b?a:b;}
int dfs(int w,int f){
	if(w==T)return f;
	int used=0;
	for(int&i=e1[w];i;i=e[i].nx)if(e[i].v){
		int u=e[i].to;
		if(h[u]!=h[w]+1)continue;
		int c=dfs(u,min(f-used,e[i].v));
		e[i].v-=c,e[i^1].v+=c,used+=c;
		if(f==used)return f;
	}
	h[w]=0;
	return used;
}
void ae(int a,int b,int c1,int c2=0){
	e[ep]=(edge){b,c1,e0[a]};e0[a]=ep++;
	e[ep]=(edge){a,c2,e0[b]};e0[b]=ep++;
}
int n,m;
char s[107][107];
int main(){
	scanf("%d%d",&n,&m);
	S=n+m+1,T=S+1;
	for(int i=1;i<=n;++i){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j)if(s[i][j]!='.'){
			if(s[i][j]=='S'){
				ae(S,i,inf);
				ae(S,n+j,inf);
			}else if(s[i][j]=='T'){
				ae(i,T,inf);
				ae(n+j,T,inf);
			}else{
				ae(i,n+j,1,1);
			}
		}
	}
	int ans=0;
	while(bfs())ans+=dfs(S,inf*2);
	if(ans>n*m)ans=-1;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
s = list(input())
N = int(len(s))
a = int(((N-1)/2))
b = int(((N+3)/2))
s1 = s[0:a]
s2 = s[b:N-1]
if s1 == list(reversed(s1)) and s2 ==list(reversed(s2)) and s ==list(reversed(s)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
	"strings"
)

type Node struct {
	Key int
	Parent *Node
	Left *Node
	Right *Node
}

const MAX int = 500000
var root *Node
var pos int
var outKeys []int = make([]int, MAX)

func insert(k int) {
	insertNode := &Node{Key: k}
	var x *Node = root
	var y *Node = nil

	for {
		if x==nil {
			break
		}
		y = x
		if insertNode.Key < x.Key {
			x = x.Left
		} else {
			x = x.Right
		}
	}
	insertNode.Parent = y
	if y==nil {
		root = insertNode
	} else if insertNode.Key < y.Key {
		y.Left = insertNode
	} else {
		y.Right = insertNode
	}
}

func inorder(u *Node) {
	if u==nil {
		return
	}
	inorder(u.Left)
	outKeys[pos] = u.Key
	pos ++
	inorder(u.Right)
}

func preorder(u *Node) {
	if u==nil {
		return
	}
	outKeys[pos] = u.Key
	pos ++
	preorder(u.Left)
	preorder(u.Right)
}

func print() {
	fmt.Printf(" %s\n", strings.TrimRight(fmt.Sprintf("%+v", outKeys[:pos])[1:], "]"))
}

func nextStr(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	N := nextInt(scanner)
	for i:=0; i<N; i++ {
		cmd := nextStr(scanner)
		if cmd == "insert" {
			v := nextInt(scanner)
			insert(v)
		} else {
			pos = 0
			inorder(root)
			print()
			pos = 0
			preorder(root)
			print()
			pos = 0
		}
	}
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

const int MAXN = 100010;

int n;
int a[MAXN];

int main()
{
	
	scanf("%d", &n);
	map<int, int> F;
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%d", &a[i]);
		F[a[i]] ++;
	}
	sort(a+1, a+n+1);
	if (a[n]-a[1] >= 2)
	{
		puts("No");
		return 0;
	}
	if (F.size() == 1)
	{
		if (a[1] == n-1 || a[1] <= n/2)
			puts("Yes");
		else
			puts("No");
		return 0;
	}
	int x = F[a[n]];
	if (a[n] > n-x && x/2+n-x >= a[n])
		puts("Yes");
	else
		puts("No");
	
	
	return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
main(){
  string s,t;
  int l,i;
  while(cin>>s>>l,l){
    map<string,int>m;
    m.insert({s,0});
    for(i=1;;++i){
      for(;s.size()<l;)s+='0';
      sort(s.begin(),s.end());
      t=s;
      sort(s.rbegin(),s.rend());
      int x=stoi(s),y=stoi(t);
      s=to_string(abs(x-y));
      if(m.find(s)!=m.end())break;
      m.insert({s,i});
    }
    int x=m.find(s)->second;
    cout<<x<<' '<<s<<' '<<i-x<<endl;
  }
}

Measured memory_bytes: 3280
N, M = map(int, input().split())
Path = [0 for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    Path[b-1] += 1
    if a > 1:
        Path[a-1] += 1

for p in Path:
    if p % 2 != 0:
        print("NO")
        break
else: print("YES")

Measured memory_bytes: 3888
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long long n;
  long long ans=0;
  cin >> n;
  vector<long long> a(n+1);
  for(long long i=0; i<=n; i++) {
    cin >> a[i];
  }

  for(long long i=0; i<n; i++) {
    long long b;
    cin >> b;

    if(a[i] <= b) {
      ans += a[i];
      b -= a[i];
    } else {
      ans += b;
      b=0;
    }
    // cout << "b : "<< b << endl;

    if(a[i+1] <= b) {
      ans += a[i+1];
      a[i+1]=0;
    } else {
      ans += b;
      a[i+1] -= b;
    }

    // cout << i << " : ";
    // for(long long i=0; i<=n; i++) cout << a[i] << " ";
    // cout << endl;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=(1e6)+10;
const int INF=(1e9);
int n,sum[maxn],mx[maxn];
char s[maxn];

int solve(int mid) {
	int mn=0,now=0,mxx=0;
	for (int i=1;i<=n;i++) {
		if (s[i]=='?') {
			if (mx[i]+2+now<=mid) {
				now+=2;
			}
		}
		mn=min(mn,sum[i]+now);
		mxx=max(mxx,sum[i]+now);
	}
	if (mxx>mid) return INF;
	return mid-mn;
}
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	for (int i=1;i<=n;i++) {
		sum[i]=sum[i-1];
		if (s[i]=='1') sum[i]++;
		else sum[i]--;
	}
	mx[n]=sum[n];
	for (int i=n-1;i>=1;i--)
		mx[i]=max(mx[i+1],sum[i]);
	//for (int i=0;i<=n;i++) printf("%d ",solve(i)); printf("\n");
	int l=0,r=n-1,res=n,mid,ans=2*n;
	while (l<=r) {
		mid=(l+r)/2;
		if (solve(mid)<solve(mid+1)) r=mid-1,res=mid;
		else l=mid+1;
	}
	for (int i=res-10;i<=res+10;i++)
		if (0<=i&&i<=n) ans=min(ans,solve(i));
	printf("%d\n",ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Measured memory_bytes: 12612
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,h[100005],dp[100005]={};
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>h[i];
  dp[2]=abs(h[2]-h[1]);
  for(int i=3;i<=n;i++){
    dp[i]+=min(abs(h[i]-h[i-2])+dp[i-2],abs(h[i]-h[i-1])+dp[i-1]);
  }
  cout<<dp[n]<<endl;
  return(0);
}


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

#define rep(i, n) for ( ll i = 0; i < (n); ++i )
#define reps(i, n) for ( ll i = 1; i <= (n); ++i )
#define _rep(i, n) for ( ll i = (n) - 1; i >= 0; --i )
#define _reps(i, n) for ( ll i = n; i > 0; --i )
#define all(x) (x).begin(), (x).end()
#define _all(x) (x).rbegin(), (x).rend()

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



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

	map<ll, ll>	l, r;
	reps( i, n ) {
		ll a;
		cin >> a;
		if ( i + a <= n ) {
			l[i + a]++;
		}
		if ( i - a >= 0 ) {
			r[i - a]++;
		}
	}

	ll cnt = 0;
	for( ll i = 0; i <= n; i++ ) {
		cnt += (l[i] * r[i]);
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 28644