akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
total = 0
before = -2
for i in range(N):
  menu = A[i] - 1
  total += B[menu]
  if menu == before+1:
    total += C[before]
  before = menu
print(total)

Measured memory_bytes: 3064
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


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;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


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


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




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

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  while(1){
    ll n;cin>>n;
    if(n==0) return 0;
    vector<string> v(n);
    rep(i,n) cin>>v[i];
    ll ans=0;
    rep(i,n-1) if((v[i]=="lu" && v[i+1]=="ru") || (v[i]=="ru" && v[i+1]=="lu") || (v[i]=="ld" && v[i+1]=="rd") || (v[i]=="rd" && v[i+1]=="ld")) ans++;
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 3168
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 999999999
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);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 MOD(x) (x%(mod))
using namespace std;

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

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

char d[55][55];
int black,white;
int w,h;

void init(){
  rep(i,55){
    rep(j,55){
      d[i][j]='.';
    }
  }
  black=white=0;
}

void bfs(int sy,int sx){
  d[sy][sx]='#';
  if(debug)cout<<"start"<<endl;
  if(debug)rep(i,h){rep(j,w)cout<<d[i][j]<<" ";cout<<endl;}
  int cnt=1;
  bool bb=false,ww=false;
  queue<int>q;
  q.push(sx);q.push(sy);
  while(!q.empty()){
    int x,y;
    x=q.front();q.pop();
    y=q.front();q.pop();
    rep(i,4){
      if(0<=x+dx[i]&&x+dx[i]<w&&0<=y+dy[i]&&y+dy[i]<h&&d[y+dy[i]][x+dx[i]]!='#'){
	if(d[y+dy[i]][x+dx[i]]=='W'){
	  ww=true;
	}else if(d[y+dy[i]][x+dx[i]]=='B'){
	  bb=true;
	}else{
	  cnt++;
	  q.push(x+dx[i]);q.push(y+dy[i]);
	  d[y+dy[i]][x+dx[i]]='#';
	}
      }
    }
  }
  if(!bb&&ww)white+=cnt;
  else if(bb&&!ww)black+=cnt;
}

int main(){
  while(cin>>w>>h){
    if(w==0&&h==0)break;
    init();
    rep(i,h)rep(j,w)cin>>d[i][j];
    rep(i,h)rep(j,w)if(d[i][j]=='.')bfs(i,j);
    cout<<black<<" "<<white<<endl;
  }

  return 0;
}

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

int main(){
    int n; cin >> n;
    set<int> s;
    rep(i,n){
        int a; cin >> a;
        s.insert(a);
    }
    cout << s.size() << endl;

}

Measured memory_bytes: 3616
//file_name:ABC54_A.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Alice");}else{puts("Bob");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    ll a[2] = {};
    rep(i,2){
        scanf("%lld",&a[i]);
        if(a[i]==1)a[i]+=13;
    }

    if(a[0]==a[1]){
        puts("Draw");
        return 0;
    }
    if(a[0]>a[1])yn;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <typename T> bool chmax(T &a, const T &b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> bool chmin(T &a, const T &b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
const long long MOD = 1e9 + 7;

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll m = LLONG_MIN;
    chmax(m, a * c);
    chmax(m, a * d);
    chmax(m, b * c);
    chmax(m, b * d);
    cout << m << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

  if (X == 3 || X == 5 || X == 7) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld double
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pll pair <ll,ll>
#define nl "\n"
ll n,wt;
ll w[102], v[102];
ll dp[102][100005]; 
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>wt;
	ll i,j;
	for(i=0;i<n;i++)
		cin>>w[i]>>v[i];
	for(i=0;i<102;i++)
		for(int j=0;j<100005;j++)
			dp[i][j]=-1;
	for(i=0;i<=wt;i++)
		dp[n-1][i] = (i<w[n-1])?0:v[n-1];
	for(i=n-2;i>=0;i--)
	{
		for(j=wt;j>=0;j--)
		{
			dp[i][j] = dp[i+1][j];
			if(j >= w[i])
				dp[i][j] = max(dp[i+1][j-w[i]] + v[i], dp[i][j]);
		}
	}
	cout<<dp[0][wt]<<nl;
	return 0;
}

Measured memory_bytes: 83348
#include<stdio.h>
int main(){
  int A[101], n, i, j, t, sw = 0;

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

  for ( i = 1; i <= n; i++ ){
    for ( j = n; j >= i+1; j-- ){
      if ( A[j] < A[j-1] ){
	t = A[j]; A[j] = A[j-1]; A[j-1] = t;
	sw++;
      }
    }
  }

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

  return 0;
}


Measured memory_bytes: 2144
#define _CRT_DISABLE_PERFCRIT_LOCKS
#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define ifor for(i=0; i<n; i++)

using namespace std;



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

    ll a, b;
    cin>>a>>b;
    cout<<(a+b)%24<<endl;

    return 0;
}


Measured memory_bytes: 256
int N, K;
char s[11];
int main(){
	scanf("%d%s%d", &N, s, &K);
	K--;
	for(int i=0; i<N; i++){
		putchar(s[i]==s[K]?s[K]:'*');
	}
	putchar(10);
	return 0;
}


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

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ar array
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
const ll inf = 2e9 + 5;
double PI = 3.14159265358979323846;

void solve() {

    ll n, m;
    cin >> n >> m;
    char grid[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }

    vvi dp(n + 1, vi(m + 1, 0));
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == '#') {
                dp[i][j] = 0;
            } else {
                if (i - 1 > 0)dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
                if (j - 1 > 0)dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
            }
        }
    }

    cout << dp[n][m] << endl;

}

int32_t main()
{
    IOS
    // int T; cin >> T; while (T--)
    solve();
    return 0;
}


Measured memory_bytes: 8176
#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;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  if(A[0]!=0){
    cout<<-1<<endl;
    return 0;
  }
  for(int i=1;i<N;i++){
    if(A[i+1]-A[i]>1){
      cout<<-1<<endl;
      return 0;
    }
  }
  int now=A[N-1];
  ll ans=0;
  for(int i=N-2;i>=0;i--){
    if(now<=A[i])ans+=now;
    else if(now==A[i])ans++;
    else ans+=now-A[i];
    now=A[i];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1024
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    d = collections.defaultdict(int)
    for _ in range(N):
        s = S()
        d[s] += 1
    v_max = 0
    for k, v in d.items():
        v_max = max(v, v_max)
    sts = []
    for k, v in d.items():
        if v == v_max:
            sts.append(k)
    sts = sorted(sts)
    for string in sts:
        print(string)

main()



Measured memory_bytes: 35504
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int cnt[200000];
vector<long long>v;
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(c==0){
		printf("0\n");return 0;
	}
	b--;
	unsigned long long x=c;
	for(int i=0;i<a;i++){
		cnt[((long long)x)/(1LL<<47)+100000]++;
		x^=x<<13;
		x^=x>>7;
		x^=x<<17;
	}
	int at=0;
	for(int i=0;i<200000;i++){
		if(b<cnt[i]){
			at=i;
			break;
		}else b-=cnt[i];
	}
	//printf("%d\n",at);
	x=c;
	for(int i=0;i<a;i++){
		if(((long long)x)/(1LL<<47)+100000==at){
			v.push_back((long long)x);
		}
		x^=x<<13;
		x^=x>>7;
		x^=x<<17;
	}
	std::sort(v.begin(),v.end());
	printf("%lld\n",v[b]);
}

Measured memory_bytes: 1576
from collections import deque
from itertools import product
from copy import deepcopy

h, w = map(int, input().split())
ls = [list(input()) for _ in range(h)]

sls = list(product(range(h),range(w)))
ans = 0
move = [[0,1], [1,0],[0,-1], [-1,0]]
for s in sls:
    if ls[s[0]][s[1]] == '#':
        continue
    else:
        lss = deepcopy(ls)
        d=deque()
        d.append(s)
        lss[s[0]][s[1]] = 0
        while d:
            x,y = d.popleft()
            c = lss[x][y]
            for dx,dy in move:
                if 0<=x+dx<h and 0<=y+dy<w and lss[x+dx][y+dy] == '.' :
                    lss[x+dx][y+dy] = c+1
                    d.append([x+dx, y+dy])
                    

        dist = 0
        for i in range(h):
            for j in range(w):
                if type(lss[i][j]) is int:
                    dist = max(dist, lss[i][j])

        ans = max(ans, dist)

print(ans)


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

typedef long long ll;
ll INFL = 1ll << 60;

int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<ll>> g(V, vector<ll>(V, INFL * 2));
  for (int i = 0; i < E; i++) {
    int s, t, d;
    cin >> s >> t >> d;
    g[s][t] = d;
  }
  for (int i = 0; i < V; i++) g[i][i] = 0;

  for (int k = 0; k < V; k++)
    for (int i = 0; i < V; i++)
      for (int j = 0; j < V; j++) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

  for (int i = 0; i < V; i++) {
    if (g[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }

  for (int y = 0; y < V; y++) {
    for (int x = 0; x < V; x++) {
      if (g[y][x] >= INFL)
        cout << "INF";
      else
        cout << g[y][x];
      if (x != V - 1) cout << " ";
    }
    cout << endl;
  }
}



Measured memory_bytes: 3252
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;


int main() 
{  
	int a;
	cin >> a;
	int s;
	cin >> s;
	int saityou = 0;
	for (int b = 0; b < a; b++) {
		int c, d;
		cin >> c >> d;
		s += c - d;
		if (s < 0) { cout << 0 << endl; goto i; }
		if (saityou < s)saityou = s;
	}
	cout << saityou << endl;
i:;
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N, x;
int a[110000];
signed main() {
    cin >> N >> x;
    rep(i, N) { cin >> a[i]; }
    int ans = 0;
    for (int i = 1; i < N; i++) {
        int k = max(0LL, a[i - 1] + a[i] - x);
        int n = min(a[i], k);
        a[i] -= n;
        ans += k;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
def solve():
  N, M = map(int, input().split())
  lis = [False]*N
  cnt = [1]*N
  lis[0] = True
  for i in range(M):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    if lis[x]==True:
      lis[y]=True
      if cnt[x]==1:
        lis[x]=False
    cnt[x] -= 1
    cnt[y] += 1
  ans = lis.count(True)
  return ans
print(solve())

Measured memory_bytes: 75956
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


struct mint {
	int x;
	mint(int x = 0) :x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= MOD)x -= MOD;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += MOD - a.x) >= MOD)x -= MOD;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint a)const {
		return mint(*this) += a;
	}
	mint operator-(const mint a)const {
		return mint(*this) -= a;
	}
	mint operator*(const mint a)const {
		return mint(*this) *= a;
	}
	mint pow(int t)const {
		if (!t)return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1)a *= *this;
		return a;
	}

	//for prime mod
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a)const {
		mint res(*this);
		return res /= a;
	}
};
ostream& operator<<(ostream& os, const mint& m) {
	os << m.x;
	return os;
}

signed main() {
	int N;
	cin >> N;
	vector<int>A(N);
	rep(i, N)cin >> A[i];
	map<int, int>m;
	rep(i, N)m[A[i]]++;
	bool can = true;
	if (N & 1)if (m[0] != 1)can = false;
	int init;
	if (N & 1)init = 2;
	else init = 1;
	for (int i = init; i <= N; i += 2) {
		if (m[i] != 2)can = false;
	}
	if (!can) {
		cout << 0 << endl;
		return 0;
	}
	mint ans = 2;
	ans = ans.pow(N / 2);
	cout << ans << endl;
}

Measured memory_bytes: 6144
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うためスコアと重みはマイナスの値

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place]: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

int main(){
    ll N;
    cin >> N;
    vll p(N);
    rep(i, N){
        cin >> p[i];
    }

    auto check = [&](){
        rep(i, N-1){
            if(p[i]>p[i+1]){
                return false;
            }
        }
        return true;
    };

    if(check()){
        cout << "YES" << endl;
        return 0;
    }

    rep(i, N-1){
        REP(j, i+1, N){
            swap(p[i], p[j]);
            if(check()){
                cout << "YES" << endl;
                return 0;
            }
            swap(p[i], p[j]);
        }
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
int main ()
{
  long long N, A, B;
    cin >> N >> A >> B;
    
    long long res;
    if (A > B || (N == 1 && A != B)) res = 0;
    else res = (B - A) * N -2 * (B - A) +1; 
    cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int s = sc.nextInt();
		sc.close();
		
		
		int numOfs = 0;
		
		for(int i = 0; i < n; i ++) {
			if(numOfs != k) {
				System.out.print(s);
				numOfs++;
			}else {
				
				if(s == 1000000000) {
					System.out.print(s-1);
				}else {
					System.out.print(s+1);
				}
			}
			if(i != n - 1) {
				System.out.print(" ");
			}
			System.out.flush();
		}
		System.out.print("\n");
		System.out.flush();
	}
}


Measured memory_bytes: 42424
#include<iostream>
#include<cstdio>
//This code is written by Itst
using namespace std;

const int MOD = 1e9 + 7;
int N , M , dp[3007][3007][2];

inline void add(int &a , int b){a += b; if(a > MOD) a -= MOD;}

int main(){
	cin >> N >> M;
	for(int i = 0 ; i <= N ; ++i)
		dp[0][i][i == 0] = 1;
	for(int i = 0 ; i < M ; ++i)
		for(int j = 0 ; j <= N ; ++j)
			for(int k = 0 ; k < 2 ; ++k)
				if(dp[i][j][k]){
					if(j){
						add(dp[i + 1][j - 1][k | (j == 1)] , dp[i][j][k]);
						add(dp[i + 1][j][k | (j == 1)] , dp[i][j][k]);
					}
					if(j != N){
						add(dp[i + 1][j + 1][k] , dp[i][j][k]);
						add(dp[i + 1][j][k] , dp[i][j][k]);
					}
				}
	int sum = 0;
	for(int i = 0 ; i <= N ; ++i) add(sum , dp[M][i][1]);
	cout << sum;
	return 0;
}


Measured memory_bytes: 70784
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

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

	ll s;  cin >> s;
  	ll x = (INF - s % INF) % INF;
  	ll y = (s + x) / INF;
	printf("0 0 1000000000 1 %lld %lld\n", x , y);

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int n;
  while(cin>>n){
    if(n==0) break;
    vector<string> grid(n);
    REP(i,n){
      cin>>grid[i];
    }  
    bool find =false;
    for(int size=1; size<=n; size++){
      find = false;
      for(int l=0; l+size<=n; l++){
        for(int h=0; h+size<=n; h++){
          bool f = true;
          for(int x=l; x<l+size; x++){
            for(int y=h; y<h+size; y++){
              if(grid[y][x]=='*'){
                f = false;
                break;
              }
            }
            if(!f) break;
          }
          if(f){
            find=true;
            break;
          }
        }
        if(find) break;
      }
      if(!find){
        cout<<size-1<<endl;
        find = true;
        break;
      }else if(size==n){
        cout<<n<<endl;
      }
    }
  }
  return 0;
}

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

int n,m;
priority_queue <int> q;
long long ans=0;
int main(){
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		int o;
		cin >> o;
		q.push(o);
	}
	for (int i = 0; i < m; ++i)
	{
		int tmp=q.top();
		q.pop();
		q.push(tmp/2);
	}
	while(q.size())
	{
		int tmp=q.top();
		q.pop();
		ans+=tmp;		
	}
	cout << ans;
}

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

int main(void){
    int N;
    cin>>N;
    int l[N],r[N];
    int ans=0;

    for(int i=0;i<N;i++){
        cin>>l[i]>>r[i];
        ans+=r[i]-l[i]+1;
    }
    cout<<ans<<endl;
    return 0;
}


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

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mxx=2e5+7;
vector<int> adj[mxx];
bool vis[mxx];int cnt;
void dfs(int u)
{
	 vis[u]=true;cnt++;
	 for(auto x:adj[u])
	 {
	 	 if(!vis[x])dfs(x);
	 }
}
int main()
{
     
    fast
   
   int n,m;
   cin>>n>>m;
   for(int i=0;i<m;i++)
   {
   	  int x,y;
   	  cin>>x>>y;
   	  adj[x].push_back(y);
   	  adj[y].push_back(x);
   }
   memset(vis,false,sizeof vis);
   int ans=1;
   for(int i=1;i<=n;i++)
   {
   	 if(!vis[i])
   	 {
   	 	  cnt=0;
          dfs(i);
          ans=max(ans,cnt);
   	 }
   }
   cout<<ans;

}

Measured memory_bytes: 20980
struct T{int a,b;}A[3333];long P[3333],M=1e9+7,F[2<<17],I[2<<17]={1},X;i,j,k,t;c(a,b)struct T*a,*b;{t=a->a-b->a?:a->b-b->b;}p(a,b){return b?p(a%M*a%M,b/2)*(b%2?a:1L)%M:1;}f(a,b){return F[a+b]*I[a]%M*I[b]%M;}main(s){for(;++X<2<<17;)I[X]=p(s=F[X]=X*s%M,M-2);for(k=A;~scanf("%d",k);k+=4)i++-1||gets(P);for(qsort(A,i/=2,8,c);j<i;P[j++]=X)for(X=f(s=A[k=j].a-=1,t=A[j].b-=1);k--;)X=t<A[k].b?X:(X-f(s-A[k].a,t-A[k].b)*P[k]%M+M)%M;printf("%d",X);}

Measured memory_bytes: 4352
using System.Linq;
using System.Numerics;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split();
	public K()
	{
		var N = F;
		var ps = new Complex[N];
		for (var i = 0; i < N; i++) { var I = G; ps[i] = new Complex(I[0], I[1]); }
		var M = 100000;
		var d = 2 * PI / M;
		var ans = new int[N];
		for (var i = 0; i < M; i++)
		{
			var p = Complex.FromPolarCoordinates(1, i * d);
			var k = -1;
			var r = double.NegativeInfinity;
			for (var j = 0; j < N; j++)
			{
				var tmp = (p * ps[j]).Real;
				if (tmp > r) { r = tmp; k = j; }
			}
			ans[k]++;
		}
		for (var i = 0; i < N; i++) WriteLine(ans[i] / (decimal)M);
	}
}


Measured memory_bytes: 13396
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;

void main() {
  int n, m, v, p;
  readf (" %d %d %d %d", &n, &m, &v, &p);
  auto a = new int[n];
  foreach (i; 0 .. n) readf (" %d", &a[i]);
  //+v
  sort!"a>b" (a);
  int res = p;
  auto s = new long[n+1];
  foreach (i; 0 .. n) {
    s[i+1] = s[i] + a[i];
  }
  foreach (i; p .. n) {
    int x = a[i] + m;
    if (x < a[p-1]) break;
    int q = (v - 1) - (p - 1);
    q -= (n - 1 - i);
    if (q <= 0) {
      res = i + 1;
      continue;
    }
    long e = (i - (p - 1)).to!long * x;
    e -= s[i] - s[p-1];
    //q - votes
    //m - judges
    //t <= x * q
    if (e >= m.to!long * q) {
      res = i + 1;
    }
  }
  writeln (res);
}



Measured memory_bytes: 3452
//
// Created by inoue on 2019-11-09.
//

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x)
#define debug(x)
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
    string s;
    cin >> s;

    int val = 0;

    int n = s.size()+1;
    vint l(n);
    vint r(n);

    rep(i, n-1) {
        if (s[i] == '<'){
            val++;
        }
        else {
            val = 0;
        }

        l[i+1] = val;
    }

    val = 0;
    for(int i=n-1; i>=0; i--) {
        if (s[i] == '>') {
            val++;
        }
        else {
            val = 0;
        }

        r[i] = val;
    }

    ll ans = 0;
    rep(i, n) {
        ans += max(l[i], r[i]);
//        cout << l[i] << " " << r[i] << endl;
//        cout << max(l[i], r[i]) <<  " ";
    }
//    cout << endl;

    cout << ans << endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 4856
#include <stdio.h>
int main()
{
  int a,b;
  char op;
  scanf ("%d %c %d",&a,&op,&b);
  while(op!='?'){
    if(op=='+'){
      printf("%d\n",a+b);
    }else if(op=='-'){
      printf("%d\n",a-b);
    }else if(op=='*'){
      printf("%d\n",a*b);
    }else {
      printf("%d\n",a/b);
    }
    scanf("%d %c %d",&a,&op,&b);
  }
  return 0;
}

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

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  repI(i, 1, n+1) {
    if (i % 3 != 0 && i % 5 != 0) ans += i;
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 3636
def swap(a, i, j):
    # list aのi番目の要素とj番目の要素を交換する関数
    k = a[j]
    a[j] = a[i]
    a[i] = k


def selectionSort(a, n):
    sw = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j] < a[minj]:
                minj = j
        if i != minj:
            sw += 1
        swap(a,i,minj)
    print(' '.join(list(map(str, a))))
    print(sw)


n = int(input())
a = list(map(int, input().split()))
selectionSort(a, n)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
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; }

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    ll w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;

    if (x - r >= 0 && x + r <= w && y - r >= 0 && y + r <= h) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3212
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // long long64_t, long long*_t
#include <cstdio> // prlong longf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;
vector<int> par;
vector<int> RANK;

//初期化,par[i]==iなら根だしRANK=0なら何も繋がってない
void init(int n){
  for(int i=0; i<n; i++){
    par.push_back(i);
    RANK.push_back(0);
  }
  return;
}

//根を返す関数
int root(int x){
  if(par[x]==x){
    return x;
  }
  return par[x]=root(par[x]);//経路圧縮
}

//xとyが同じ集合に属するか否か．
bool same(int x, int y){
  return root(x)==root(y);
}

//xとyの属する集合を併合
void merge(int x, int y){
  x=root(x);
  y=root(y);
  if(x==y) return;
  if(RANK[x]<RANK[y]){
    par[x]=y;//『「元のx」の根』の根を「元のy」の根にする（高い方につなげるので）
  }
  else{
    par[y]=x;
    if(RANK[x]==RANK[y]) RANK[x]++;//根に同じ長さのが増えるから高さが1つ増える
  }
  return;
}

int main(){
  int n,m;
  cin >> n >> m;
  init(n);
  for(int i=0; i<m; i++){
    int x,y,z;
    cin >> x >> y >> z;
    merge(x-1,y-1);
  }
  int sum=1;
  vector<int> isroot(n);
  for(int i=0; i<n; i++) isroot[i]=root(i);
  sort(isroot.begin(),isroot.end());
  for(int i=0; i<n-1; i++){
    if(isroot[i]!=isroot[i+1]) sum++;
  }
  cout << sum << endl;
}


Measured memory_bytes: 1652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; i++)
#define all(a) (a).begin(), (a).end()

int A, B, C;

int main () {
  cin >> A >> B >> C;

  cout << max(C-(A-B), 0) << endl;
  return 0;
}


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

long long int hantei(long long int x){
	if(x==1){
    	return 1;
    }
  	else{
    	long long int s = 2*hantei(x/2) + 1;
      return s;
    }
}

int main() {
	long long int a;cin>>a;
    int ans,b,c; ans=0;b=0;c=1;
  
	cout<<hantei(a)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,w,r,s;
char c[200001];
int main()
{ cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  { cin>>c[i];
    if(c[i]=='R')
       r++;
    else
       w++;
  }
  for(int i=1;i<=r;i++)
    if(c[i]=='W')
       s++;
  cout<<s<<'\n';
  return 0;
}


Measured memory_bytes: 3804
#include <algorithm>
#include <cstring>
#include <numeric>
#include <iostream>
using namespace std;
int n, k;
int a[500];

bool check(int d) {
    int b[n];
    for (int i = 0; i < n; i++) b[i] = a[i]%d;
    int s = accumulate(b, b+n, 0);
    if (s % d != 0) return false;
    sort(b, b+n);
    int r = s/d;
    int sum = 0;
    for (int i = 0; i < n; i++) if (i < n-r) sum += b[i]; else sum += d - b[i];
    return sum <= 2 * k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    int s = accumulate(a, a+n, 0);
    int ans = 1;
    for (int d = 1; d*d <= s; d++) {
        if (check(s/d)) { cout << s/d << endl; return 0; }
        if (check(d)) ans = max(ans, d);
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
N,S = map(int,input().split())

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

    
print (ans)


Measured memory_bytes: 47580
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int a, b, k;
	cin >> a >> b >> k;
	
	int ans = 0;
	for(int i = 100; i >= 1; i--) {
		if( a % i == 0 && b % i == 0 ) {
			k--;
			
			if( k == 0 ) {
				ans = i;
				break;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


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

vector< vector<int> > arr;

int main(){
	int n,d;
	cin>>n>>d;
	for(int i=0;i<n;i++){
		vector<int> v;
		for(int j=0;j<d;j++){
			int x;
			cin>>x;
			v.push_back(x);
		}
		arr.push_back(v);
	}
	int ans=0;
	for(int k=0;k<n;k++){
		for(int q=k+1;q<n;q++){
			double sum=0;
			for(int z=0;z<d;z++){
				sum+=pow(abs(arr[k][z]-arr[q][z]), 2);
			}
			sum=sqrt(sum);
			if(floor(sum)==ceil(sum))ans++;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 3728
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  string S;
  cin >> S;
  const char* s = S.c_str();

  ll ans = 1;
  ll size = 1;
  ll minus = 0;
  string recent = S.substr(0, 1);
  REP(i, 1, S.size()) {
    string current = S.substr(i + minus, size);
    if (recent != current) {
      ans++;
      recent = S.substr(i, size);
      size = 1;
      minus = 0;
    } else {
      size++;
      minus--;
    }
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

void add(set<string> &ans, string s1, string s2) {
    ans.insert(s1 + s2);

    reverse(all(s1));
    ans.insert(s1 + s2);

    reverse(all(s2));
    ans.insert(s1 + s2);

    reverse(all(s1));
    ans.insert(s1 + s2);

    reverse(all(s2));
    ans.insert(s1 + s2);
}

void solve() {
    string s;
    cin >> s;
    set<string> ans;
    rep(i, s.size()) {
        int a = i;
        int b = s.size() - i;
        if (a == 0 || b == 0) continue;
        auto s1 = s.substr(0, a);
        auto s2 = s.substr(a, b);
        add(ans, s1, s2);
        add(ans, s2, s1);
    }
    cout << ans.size() << endl;
}
int main() {
    int m;
    cin >> m;
    rep(i, m) { solve(); }

    return 0;
}

Measured memory_bytes: 3156
import java.util.*;
import java.util.stream.IntStream;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int W = sc.nextInt();
    int[] w = new int[N];
    long[] v = new long[N];
    for (int i = 0; i < N; i++) {
      w[i] = sc.nextInt();
      v[i] = Long.parseLong(sc.next());
    }
    long[] dp = new long[W+1];
    for (int i = 0; i < N; i++) {
      for (int j = W-w[i]; j >= 0 ; j--) {
        dp[j+w[i]] = Math.max(dp[j+w[i]], dp[j] + v[i]);
      }
    }
    //System.out.println(Arrays.toString(dp));
    System.out.println(dp[W]);
  }
}

Measured memory_bytes: 22228
N = int(input())
A = [int(n) for n in input().split(" ")]

B = []
S = 0
for i in range(N):
    #print(A[i], B)
    if i == 0:
        B.append(A[i])
        continue
    last_B = B[i - 1]
    humidai = last_B - A[i]
    if humidai <= 0:
        humidai = 0
    now_B = A[i] + humidai
    #print(humidai)
    S += humidai
    B.append(now_B)

print(S)
    


Measured memory_bytes: 32324
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const long long INFL = 2e18;
const int MOD = 1000000007;
int main(){
	int n;
	cin >> n;
	vector<int> l(n);
	for(int i = 0;i < n;i++)cin >> l[i];

	sort(l.begin(),l.end());

	ll ans = 0;
	for(int i = 0;i < n-1;i++){
		for(int j = i+1;j < n;j++){
			auto p = lower_bound(l.begin(),l.end(),l[i]+l[j]);
			auto q = upper_bound(l.begin(),l.end(),l[j]-l[i]);
			int cnt = p - q;
			cnt--;//l[j]は必ず選ばれる
			if(l[i] > l[j] - l[i])cnt--;
			ans += cnt;
		}
	}
	cout << ans / 3 << endl;
}


Measured memory_bytes: 3592
//
// Create by 神舟 on 2015-02-20
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <set>
#include <vector>
using namespace std;

#define CLR(x) memset(x,0,sizeof x)
#define ll long long
#define inf 0x3f3f3f3f
const int maxn=1e5+5;
const int MOD=5e5+5;
int n,flag,num[maxn],l[maxn],r[maxn];
void dfs(int ln,int rn)
{

    if(ln+rn==10) flag=1;
    if(flag) return;
    if(num[ln+rn+1]>l[ln]){
        l[ln+1]=num[ln+rn+1];
        dfs(ln+1,rn);
    }
    if(num[ln+rn+1]>r[rn]){
        r[rn+1]=num[ln+rn+1];
        dfs(ln,rn+1);
    }
}
int main()
{
#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	ios_base::sync_with_stdio(0);

	scanf("%d",&n);
	while(n--){
        flag=0;
        CLR(l);
        CLR(r);
        CLR(num);
        l[0]=r[0]=-inf;
        for(int i=1;i<11;scanf("%d",num+i++));
        dfs(0, 0);
        if(flag) printf("YES\n");
        else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 2372
#include <stdio.h>

int main(){
  int a, b, s1, s2, x, i;

  scanf("%d %d", &a, &b);

  s1 = 0;
  s2 = 0;
  for (i = 1; i <= 999; i++) {
    s1 = (i * (i + 1)) / 2;
    s2 = ((i + 1) * (i + 2)) / 2;
    if (s1 - a == s2 - b) {
      x = s1 - a;
      break;
    }
  }

  printf("%d\n", x);

  return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <utility>
#include <memory>
#include <valarray>

using namespace std;

using ll = long long int;
#define loop(i, N) for (int i = 0; i < N; ++i)
#define scanInt(x) int x; scanf("%d", &x); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &x); getchar();
#define scanVecInt(A, N) vector<int> A(N); loop(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); loop(i, N){scanf("%lld", &(A[i])); getchar();}

constexpr int mod = 1000000007;

// modをとった和を返す
inline
int modPlus(int a, int b){return (a + b) % mod;}

// modをとった差を返す
inline
int modMinus(int a, int b){return (mod + a - b) % mod;}

// modをとった積を返す
inline
int modMultiple(int a, int b){return (static_cast<long long>(a) * b) % mod;}

int main()
{
    scanInt(N);
    scanInt(M);
    vector<int> W(N - 1);
    {
        scanInt(before);
        loop(i, N - 1){
            scanInt(x);
            W[i] = x - before;
            before = x;
        }
    }
    vector<int> H(M - 1);
    {
        scanInt(before);
        loop(i, M - 1){
            scanInt(y);
            H[i] = y - before;
            before = y;
        }
    }
    int Wsum = 0;
    loop(i, N - 1){
        Wsum = modPlus(Wsum, modMultiple(modMultiple(i + 1, N - 1 - i), W[i]));
    }
    int Hsum = 0;
    loop(i, M - 1){
        Hsum = modPlus(Hsum, modMultiple(modMultiple(i + 1, M - 1 - i), H[i]));
    }
    printf("%d\n", modMultiple(Wsum, Hsum));
}


Measured memory_bytes: 1024