akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#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()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long FINV(int n){
    if (n < 0) return 0;
    return finv[n];
}

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

/*
    Ball and Boxes 9
    男、初対面の女の子、一人以上(新歓形式)
*/

ll calc_Stirling(int n, int k){
    ll res = 0;
    rep(i,k){
        ll mul = 1;
        mul *= mod_pow(k-i, n, MOD);
        mul *= COM(k,i);
        mul %= MOD;
        if(i%2==0){
            res += mul;
            res %= MOD;
        }else{
            res -= mul;
            res += MOD;
            res %= MOD;
        }
    }
    res *= FINV(k);
    res %= MOD;
    return res;
}

int main() {
    ll n, k;
    cin >> n >> k;
    COMinit();

    ll ans = calc_Stirling(n, k);

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



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

int main(void) {
    string s;
    cin >> s;
    map<char, int> m;
    m['N'] = 0;
    m['S'] = 0;
    m['E'] = 0;
    m['W'] = 0;

    for (auto &&c : s) {
        m[c]++;
    }
    if (m['N'] == 0 && m['S'] != 0) {
        cout << "No" << endl;
        return 0;
    }
    if (m['S'] == 0 && m['N'] != 0) {
        cout << "No" << endl;
        return 0;
    }
    if (m['E'] == 0 && m['W'] != 0) {
        cout << "No" << endl;
        return 0;
    }
    if (m['W'] == 0 && m['E'] != 0) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}

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

int main() {
  long n,ans=0;
  cin >> n;
  vector<long> a(n);
  vector<bool> b(1000010);
  for(long i=0;i<n;i++) cin >> a[i];
  sort(a.begin(),a.end());
  for(long i=0;i<n;i++) {
    b[a[i]-1]=true;
    if(i!=n-1) if(a[i+1]==a[i]) continue;
    if(i!=0) if(a[i-1]==a[i]) continue;
    for(long j=1;j*j<=a[i]&&b[a[i]-1];j++) {
      if(a[i]%j==0) {
        if(b[j-1]&&a[i]!=1) b[a[i]-1]=false;
        if(b[(a[i]/j)-1]&&j!=1) b[a[i]-1]=false;
      }
    }
    if(b[a[i]-1]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long int
	#define vi vector<ll>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<ll,ll>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y) 
	#define mem(a,val) memset(a,val,sizeof(a))
	#define pb push_back
	#define f first
	#define s second
	
	using namespace std;
	
	signed main()
	{

	std::ios::sync_with_stdio(false);
	

      int n;
      cin>>n;
      std::vector<int> h(100001);
      std::vector<int> d(100001);
      for (int i = 0; i < n; ++i)
      {
      	/* code */
      	cin>>h[i];
      }
      d[1]=abs(h[1]-h[0]);
      for (int i = 2; i < n; ++i)
      {
      	d[i]=min((abs(h[i]-h[i-1])+d[i-1]),(abs(h[i]-h[i-2])+d[i-2]));
      }
      cout<<d[n-1]<<endl;
	return 0;
	}


Measured memory_bytes: 1024
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int Y = X/100;
        int Z = X-Y*100;
        // 0a+1b+2c+3d+4e+5f = Z
        // a+b+c+d+e+f = Y
        for (int f = 0; 5*f <= Z; f++) {
            for (int e = 0; 5*f+4*e <= Z; e++) {
                for (int d = 0; 5*f+4*e+3*d <= Z; d++) {
                    for (int c = 0; 5*f+4*e+3*d+2*c <= Z; c++) {
                        int b = Z-(5*f+4*e+3*d+2*c);
                        if (b < 0) {
                            continue;
                        }
                        int a = Y-(b+c+d+e+f);
                        if (a >= 0) {
                            System.out.println(1);
                            return;
                        }
                    }
                }
            }
        }
        
        System.out.println(0);
    }
}


Measured memory_bytes: 25172
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  char s[200];
  cin >> s;
  int e,m=0;
  bool q,r;
  for(int i=1;i<strlen(s);i++){
    e=0;
    for(char j='a';j<='z';j++){
      q=0;
      r=0;
      for(int k=0;k<i;k++){
        if(s[k]==j)q=true;
      }
      for(int k=i;k<n;k++){
        if(s[k]==j)r=true;
      }
      if(q&&r)e++;
    }
    if(m<e)m=e;
  }
  cout << m;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	bool sosu[100010]={1,1,0};
	for(int i=2;i<100010;i++)if(sosu[i]==false)
	for(int j=i*2;j<100010;j+=i)sosu[j]=true;
	vi so;
	rep(i,100010)if(sosu[i]==0)so.pb(i);
	int a,b,c;
	while(cin>>a>>b>>c,a+b+c){
		int oa,ob,ma=0;
		loop(i,2,a)if(sosu[i]==0){
			int t=upper_bound(all(so),a/i)-so.begin();
			t--;
			if(t==-1)continue;
			while(b*so[t]>i*c){
				if(t==0)break;
				t--;
			}
			if(b*so[t]<=i*c&&i<=so[t]){
				if(i*so[t]<=a&&i*so[t]>ma)oa=i,ob=so[t],ma=i*so[t];
			}
		}//a/i b/c<=i/so[t]
		cout<<oa<<" "<<ob<<endl;
	}
}

Measured memory_bytes: 1424
N = int(input())
t, x, y = 0, 0, 0
ok = True
for i in range(N):
    ti, xi, yi = map(int, input().split())
    t_diff = ti - t
    xy_diff = abs(xi - x) + abs(yi - y)
    if t_diff < xy_diff:
        ok = False
        break
    if t_diff == xy_diff:
        continue
    if (t_diff - xy_diff) % 2 == 1:
        ok = False
        break
    t, x, y = ti, xi, yi


print('Yes' if ok else 'No')


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define fastcin() ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(), (x).end()
#define heap priority_queue
using namespace std;
typedef pair<int, int> ii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3000; 
int n, a[maxn], s; 
bool dp[maxn][150005]; 

signed main()
{
	cin >> n; 
	for(int i = 1; i <= n; i++) 
		cin >> a[i], s += a[i]; 	
	dp[0][0] = 1; 
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= 100000; j++) {
			if(j < a[i]) dp[i][j] |= dp[i-1][a[i] - j]; 
			else dp[i][j] |= dp[i-1][j - a[i]]; 
			if(j + a[i] <= 100000) dp[i][j] |= dp[i-1][j + a[i]]; 
 		}
	}
	for(int i = 0; i <= 100000; i++) 
		if(dp[n][i]) 
			return cout << (s + i) / 2, 0; 
}


Measured memory_bytes: 206908
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int a,b,c;
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<' '<<b<<' '<<c<<endl;

    return 0;
}


Measured memory_bytes: 256
use std::io;

fn main() {
    let ab: Vec<i8> = read_input_vec();
    if ab[1] - ab[0] == ab[2] - ab[1] {
        println!("YES");
    } else {
        println!("NO");
    }
}

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

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


Measured memory_bytes: 4352
use std::collections::HashMap;

fn factors(hm: &mut HashMap<u64, u64>, mut x: u64) {
    let n = x;
    for i in 2..n + 1 {
        let c = hm.entry(i).or_insert(1);
        while x % i == 0 {
            *c += 1;
            x /= i;
        }
        if n == 1 {
            break;
        }
    }
}

fn main() {
    let n = read::<u64>();
    let mut hm = HashMap::new();
    for i in 1..n + 1 {
        factors(&mut hm, i);
    }

    //println!("{:?}", hm);

    let mut count = 1;
    for &v in hm.values() {
        count *= v;
        count %= 1000000007;
    }

    println!("{}", count);
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<'YES'<<endl;}else{cout<<'NO'<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

vi vec[200001];
int x[200001]={};
int dp[200001];
int main() {
	ll n;
	cin>>n;

	cout<<n*n*n<<endl;	
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  char last = 'A';
  int cc = 0;
  long long ans = 0;
  for (char c : string(s.rbegin(), s.rend())) {
    if (c == 'A') {
      int mv = 0;
      if (last == 'B') {
        mv = cc / 2;
      }
      ans += mv;
      cc = 2 * mv;
    } else {
      if (c != last) {
        last = c;
        ++cc;
      } else {
        cc = 1;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 788
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;

int main() {
    int N;
    string s, t;
    cin >> N >> s >> t;
    int cnt = 0;
    
    for (int i = 1; i <= N; i++) {
        if (s.substr(N - i, i) == t.substr(0 , i)) cnt = i;
    }

    cout << 2 * N - cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;


int main() {
  ll N,A,B,C,D;
  cin >> N >> A >> B >> C >> D;
  ll dif = B-A;
  //debug(dif);
  bool isok=false;
  repeat(m,N){
    ll L = C*m-D*(N-1-m);
    ll R = D*m-C*(N-1-m);
    //cerr << L << " " << R << endl;
    isok |= (L <= dif) && (dif <= R);
  }
  cout << (isok? "YES":"NO") << endl;
  return 0;
}


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

int main(){
   vector<vector <int> > A (3, vector<int>(3));
   for (int i=0; i<3; i++){
       for(int j=0; j<3; j++){
           cin >> A.at(i).at(j);
       }
   }

   int N;
   cin >> N;

   vector<int> b(N);
   for(int i=0; i<N; i++){
       cin >> b.at(i);
   }

   vector<vector <int> > table(3,vector<int>(3,0));

    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                if(b.at(i) == A.at(j).at(k)){
                    table.at(j).at(k) = 1;
                }
            }
        }
    }

    int bingo = 0;
    for(int i=0; i<3; i++){
        if(table.at(i).at(0) == table.at(i).at(1) && table.at(i).at(1) == table.at(i).at(2) && table.at(i).at(0) == 1){
            bingo ++;
            break;
        }
    }

    for(int i=0; i<3; i++){
        if(table.at(0).at(i) == table.at(1).at(i) && table.at(1).at(i) == table.at(2).at(i) && table.at(0).at(i) == 1){
            bingo++;
            break;
        }
    }

    if(table.at(0).at(0) == table.at(1).at(1) && table.at(1).at(1) == table.at(2).at(2) && table.at(0).at(0) == 1){
        bingo++;
    }

    if(table.at(0).at(2) == table.at(1).at(1) && table.at(1).at(1) == table.at(2).at(0) && table.at(0).at(2) == 1){
        bingo++;
    }

    if(bingo == 0){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#define MOD 998244353

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

long pow(long a, long b) {
	if (b == 0) return 1;
	long c = pow(a, b / 2);
	if (b % 2) c = a * c % MOD * c % MOD;
	else c = c * c % MOD;
	return c;
}

int main() {
	int N;
	cin >> N;
	vector<long> D(N), a(N);
	for (long& i : D) {
		cin >> i;
		a[i]++;
	}
	if (!D.front() && count(D.begin(), D.end(), 0) == 1) {
		sort(D.begin(), D.end());
		bool b = true;
		for (int i = 1; i < N; i++) {
			if (1 < abs(D[i - 1] - D[i])) {
				b = false;
				break;
			}
		}
		if (b) {
			long ans = 1;
			for (int i = 2; i < N; i++) {
				ans *= pow(a[i - 1], a[i]);
				ans %= MOD;
			}
			cout << ans;
		}
		else cout << 0;
	}
	else cout << 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

int main(void) {
  vector<int> ar(3);
  for (size_t i = 0; i < 3; i++) {
    cin >> ar[i];
  }
  sort(ar.begin(),ar.end());
  if (ar[0]+ar[1] == ar[2]){
    printf("Yes");
  }else{
    printf("No");
  }


}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define int long long
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }

const int P = 1e9 + 7;
const int N = 4e3 + 5;
int dp[N][N];
int32_t main() {

  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  cerr << fixed << setprecision(10);
  cin.tie(0);
  //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  
  int n, m, k;
  cin>>n>>m>>k;
  int l = (n + m - 1) / (k - 1);
  dp[0][0] = 1;
  RE (d, l) {
    REP (here, k) {
      FOR (prev_sum, 0, m) {
        int new_sum = prev_sum + here;
        dp[d][new_sum] = (dp[d][new_sum] + dp[d - 1][prev_sum]) % P;
      }
    }
  }
  int res = 0;
  for (int S = m; S > 0; S -= k - 1) {
    int lacks = (m - S) / (k - 1);
    res += dp[l - lacks][S];
    res %= P;
  }
  cout<<res<<endl; 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  return 0;
}


Measured memory_bytes: 78720
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <numeric>

using namespace std;

#define int long long
typedef long double ld;
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define vpii vector<pii>
#define vb vector<bool>
#define vbb vector<vb>
#define vs vector<string>
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define in(a, x) for (int i = x; i < (a).size(); ++i) cin >> (a)[i]
#define out(a) for (auto qwe : a) cout << qwe << " "

const int INF = 1e9;
const int INF64 = 1e18;
const int MOD = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int MOD3 = 998244353;
const int P = 37;

const int mxn = 200000;

int stress(string s, int d) {
    int c = 0;

    int x = stoi(s);

    for (int i = 1; i <= x; ++i) {
        int j = i;
        int sum = 0;
        while (j > 0) {
            sum += j % 10;
            j /= 10;
        }
        if (sum % d == 0) ++c;
    }

    return c;
}

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

    for (int test = 0; test < 1; ++test) {
        /*printf("TEST №%d\n", test);
        string s = to_string((rand() % 100000) + 1);
        int d = rand() % 30 + 1;

        int answ2 = stress(s, d);

        */string s;
        int d;
        cin >> s >> d;

        int n = s.size();

        viii dp(n + 1, vii(d, vi(10, 0)));
        vii p(n + 1, vi(d, 0));

        for (int i = 0; i < 10; ++i) {
            dp[1][i % d][i] = 1;
            p[1][i % d]++;
        }

        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < d; ++j) {
                for (int k = 0; k < 10; ++k) {
                    dp[i][j][k] = p[i - 1][(j - k + (10 * d)) % d];
                    dp[i][j][k] %= MOD;

                    p[i][j] += dp[i][j][k];
                    p[i][j] %= MOD;
                }
            }
        }

        int answ = 0;

        for (int l = 1; l < n; ++l) {
            for (int k = 1; k < 10; ++k) {
                answ += dp[l][0][k];
                answ %= MOD;
            }
        }

        reverse(all(s));

        for (int i = n - 1, sum = 0; i >= 0; --i) {
            int x = s[i] - '0';

            for (int k = (i == (n - 1)); k < x; ++k) {
                answ += dp[i + 1][((10 * d) - sum) % d][k];
                answ %= MOD;
            }

            sum += x;
            sum %= d;

            if (i == 0 && sum == 0) {
                answ = (answ + 1) % MOD;
            }
        }

        /*if (answ != answ2) {
            printf("TEST FOUND:\n%s %d\nExpected value: %d\nFound:%d", &s, d, answ2, answ);
            break;
        }*/
        cout << answ;
    }
}

Measured memory_bytes: 126080
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,a[1000010]; 
int main()
{
	scanf("%d%d",&n,&k); 
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=k+1;i<=n;i++) {
		if(a[i-k]<a[i]) puts("Yes");
		else puts("No");
	}
	return 0;
} 

Measured memory_bytes: 4540
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			int n = Integer.parseInt(br.readLine());
			
			if(n == 0){
				break;
			}
			
			boolean[] input = new boolean[2*n + 1];
			
			for(int i = 0; i < n; i++){
				input[Integer.parseInt(br.readLine())] = true;
			}
			
			ArrayList<Integer> taro = new ArrayList<Integer>();
			ArrayList<Integer> hanako = new ArrayList<Integer>();
			
			for(int i = 1 ; i <= 2*n ; i++){
				if(input[i]){
					taro.add(i);
				}
				else {
					hanako.add(i);
				}
			}
			
			//?????????????§?
			int place = 0;
			final int TARO = 0;
			final int HANAKO = 1;
			int player = TARO;
			
			int scoreT = 0;
			int scoreH = 0;
			
			while(true){
				int card;
				
				if(player == TARO){
					card = getMinimumCard(taro, place);
				}
				else {
					card = getMinimumCard(hanako, place);
				}
				
				if(card > 0){
					place = card;
					//System.out.println("Current "+place);
				}
				else {
					place = 0;
				}
				
//				int scoreT = 0;
//				int scoreH = 0;
				if(taro.size() == 0){
					scoreT = hanako.size();
					break;
				}
				else if(hanako.size() == 0){
					scoreH = taro.size();
					break;
				}
				
				if(player == TARO){
					player = HANAKO;
				}
				else {
					player = TARO;
				}
			}
			
			System.out.println(scoreT);
			System.out.println(scoreH);
		}
	}
	
	static int sum(ArrayList<Integer> list){
		int sum = 0;
		for(int i = 0; i < list.size() ; i++){
			sum += list.get(i);
		}
		
		return sum;
	}
	static int getMinimumCard(ArrayList<Integer> list, int place){
		for(int i = 0; i < list.size() ; i++){
			int tmp = list.get(i);
			if(tmp > place){
				list.remove(i);
				return tmp;
			}
		}
		
		return -1;
	}

}

Measured memory_bytes: 24312
import java.util.*;

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

        int[][] qs = new int[n][2];
        int max = 0;
        for(int i = 0; i < n; i++) {
        	qs[i][0] = sc.nextInt();
        	qs[i][1] = sc.nextInt();
        	max = Math.max(max, qs[i][1]);
        }
        boolean[] primes = new boolean[max + 1];
        Arrays.fill(primes, true);
        for(int i = 2; i <= max; i++) {
        	if(!primes[i]) continue;
        	for(int j = i * 2; j <= max; j = j + i) {
        		primes[j] = false; 
        	}
        }
        int[] preSum = new int[max + 1];
        for(int i = 3; i <= max; i++) {
        	preSum[i] = preSum[i-1];
        	if(primes[i] && primes[(i + 1) / 2]) 
        		preSum[i]++;
        }

      	for(int[] q : qs) {
      		System.out.println(preSum[q[1]] - preSum[q[0] - 1]);
      	}
    }
}


Measured memory_bytes: 102500
import Control.Applicative

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

ans :: (Int,Int,Int) -> Bool
ans (a,b,c)= a<b && b<c

main :: IO()
main = do
    [a,b,c] <- map toInt <$> words <$> getLine
    putStrLn (if (ans (a,b,c)) then "Yes" else "No")


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n;
  cin >> n;
  string s;
  map<char, int> ans, t;

  cin >> s;
  for (int j = 0; j < s.size(); ++j) ans[s[j]]++;

  for (int i = 0; i < n - 1; ++i) {
    cin >> s;
    t.clear();
    for (int j = 0; j < s.size(); ++j) t[s[j]]++;
    for (char j = 'a'; j <= 'z'; ++j) ans[j] = min(ans[j], t[j]);
  }

  for (auto a : ans)
    if (a.second > 0)
      for (int i = 0; i < a.second; ++i) cout << a.first;
  cout << endl;

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a,b,c,d,e,f;
    while(1){
            scanf("%d %d",&a,&b);
        if(a==0&&b==0)break;
        for(c=0;c<a;c++){
                printf("#");
            for(e=1;e<b-1;e++){
                    if(c==0||c==a-1){
            printf("#");
                    }else{
                printf(".");
                    }}
                printf("#\n");
            }
            printf("\n");
    }

return 0;
}

Measured memory_bytes: 588
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    try (
      Scanner sc = new Scanner(System.in);
      PrintWriter pw = new PrintWriter(System.out)) {
      int n = 1;
      
      while (true) {
        int x = sc.nextInt();

        if (x == 0) break;

        pw.append("Case " + n++ + ": " + x + "\n");
      }
      pw.flush();
    }
  }
}


Measured memory_bytes: 41544
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))


Measured memory_bytes: 63476
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    long double ans = v[0];
    for(int i = 1; i < n; i++){
        ans = (ans+v[i])/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3812
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    x,y,z = LI()
    print(z,x,y)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 38384
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int a = scanner.nextInt();
            if (a == 0)
                break;
            double sum = 0;
            int[] b = new int[a];
            for (int i = 0; i < a; i++) {
                b[i] = scanner.nextInt();
                sum += b[i];
            }
            double m = sum / a;
            double aa = 0;
            for (int i = 0; i < a; i++) {
                aa += Math.pow(b[i] - m, 2) / a;
            }
            System.out.println(Math.sqrt(aa));
 
        }
 
    }
}


Measured memory_bytes: 31076
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX/2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int n, m;
V<ll> x, y, z;

vi xs = { -1,-1,-1,-1, 1, 1, 1, 1 };
vi ys = { -1,-1, 1, 1,-1,-1, 1, 1 };
vi zs = { -1, 1,-1, 1,-1, 1,-1, 1 };
ll memo[1020][1020][8];

ll dp(int i, int j, int s) {
	if (memo[i][j][s] != -LINF)return memo[i][j][s];
	if (i == 0 || j == 0)return 0;
	if (i < j)return -LINF;
	ll eat = x[i-1] * xs[s] + y[i-1] * ys[s] + z[i-1] * zs[s];
	ll re;
	if (i > j)re = max(dp(i - 1, j - 1, s) + eat, dp(i - 1, j, s));
	else re = dp(i - 1, j - 1, s) + eat;

	memo[i][j][s] = re;
	return re;
}

int main() {


	cin >> n >> m;
	x.resize(n);
	y.resize(n);
	z.resize(n);
	rep(i, n)cin >> x[i] >> y[i] >> z[i];
	rep(i, n + 1)rep(j, m + 1)rep(k, 8)memo[i][j][k] = -LINF;


	ll ans = -LINF;

	rep(i, 8)ans = max(ans, dp(n, m, i));
	cout << ans << endl;

}

Measured memory_bytes: 64128
using System;

namespace ABC133
{
    class C
    {
        static void Main(string[] args)
        {
            long MOD = 2019;
            string[] input = Console.ReadLine().Split(' ');
            long L = long.Parse(input[0]);
            long R = long.Parse(input[1]);

            long min = MOD;
            for (long i = L; i <= R - 1; i++)
            {
                for (long j = i + 1; j <= R; j++)
                {
                    if (((i * j) % MOD) == 0)
                    {
                        Console.WriteLine(0);
                        return;
                    }

                    if (((i * j) % MOD) < min)
                    {
                        min = ((i * j) % MOD);
                    }
                }
            }
            Console.WriteLine(min);
        }
    }
}


Measured memory_bytes: 13140
from math import sqrt, ceil
def prime(n):
    if n == 2:
        return True
    for i in range(2, ceil(sqrt(n) + 0.0001)):
        if n % i == 0:
            return False
    return True

n = int(input())
for i in range(n, 2 * 10 ** 5):
    if prime(i):
        print(i)
        break



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

int main() {
  int n;
  cin>>n;
  int v[n/2],u[n/2];
  for(int i=0;i<n/2;i++)
    cin>>v[i]>>u[i];
  int cnt[2]={1,1},one[2]={},sec[2]={},utmp=0,vtmp=0;
  sort(v,v+n/2);
  sort(u,u+n/2);
  
  for(int i=1;i<n/2;i++){
    if(u[i]==u[i-1])
      cnt[0]++;
    else if(u[i]!=u[i-1]){
      if(one[0]<=cnt[0]){
        sec[0]=one[0];
        one[0]=cnt[0];
        utmp=u[i-1];
      }
      else if(cnt[0]<one[0] && cnt[0]>sec[0]){
        sec[0]=cnt[0];
      }
      cnt[0]=1;
    }
      
      
    if(v[i]==v[i-1])
      cnt[1]++;
    else if(v[i]!=v[i-1]){
      if(one[1]<=cnt[1]){
        sec[1]=one[1];
        one[1]=cnt[1];
        vtmp=v[i-1];
      }
      else if(cnt[1]<one[1] && cnt[1]>sec[1]){
        sec[1]=cnt[1];
      }
      cnt[1]=1;
    }
    
    if(i==n/2-1){
      if(one[0]<=cnt[0]){
        sec[0]=one[0];
        one[0]=cnt[0];
       
        utmp=u[i-1];
      }
      else if(cnt[0]<one[0] && cnt[0]>sec[0]){
        sec[0]=cnt[0];

      }
      if(one[1]<=cnt[1]){
        sec[1]=one[1];
        one[1]=cnt[1];
      
        vtmp=v[i-1];
      }
      else if(cnt[1]<one[1] && cnt[1]>sec[1]){
        sec[1]=cnt[1];
      
      }
    }
    
  }
    
  int ans;
    
  if(utmp!=vtmp)
    ans=n-one[0]-one[1];
  else
    ans=n-max(one[0]+sec[1],one[1]+sec[0]);
  
  cout<<ans;
    
  
  
  
}

Measured memory_bytes: 640
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, a, b = LI()
L = IR(n)
ok = max(L) // b + 1
ng = 0
while ok > ng + 1:
    mid = (ok + ng) // 2
    remain = mid
    for i in range(n):
        remain -= max(0, (L[i] - b * mid) // (a - b) + bool((L[i] - b * mid) % (a - b)))
        if remain < 0:
            ng = mid
            break
    else:
        ok = mid



print(ok)

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

int main() {
  bool yymm = true;
  bool mmyy = true;

  string s;
  cin >> s;
  string former = s.substr(0, 2);
  string latter = s.substr(2, 2);

  int a = stoi(former);
  int b = stoi(latter);

  if(a > 12 || a == 0) {
    mmyy = false;
  }

  if(b > 12 || b == 0) {
    yymm = false;
  }

  if(yymm && mmyy) {
    cout << "AMBIGUOUS" << endl;
  } else if(yymm) {
    cout << "YYMM" << endl;
  } else if(mmyy) {
    cout << "MMYY" << endl;
  } else {
    cout << "NA" << endl;
  }
}

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

int count(string s){
    if(s == "SAT") return 1;
    if(s == "FRI") return 2;
    if(s == "THU") return 3;
    if(s == "WED") return 4;
    if(s == "TUE") return 5;
    if(s == "MON") return 6;
    return 7;
}
int main(){
    string s;
    cin >> s;
    cout<<count(s)<<endl;

}

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

int main() {
    char b;  cin >> b;
    if (b == 'A')  cout << 'T' << endl;
    else if (b == 'T')  cout << 'A' << endl;
    else if (b == 'C')  cout << 'G' << endl;
    else  cout << 'C' << endl;
}

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

struct Card{
    char suit;
    char value;
};

void print(vector<Card> &a){
    for(int i=0; i<a.size(); i++){
        if(i) cout << " ";
        cout << a[i].suit << a[i].value;
    }
    cout << endl;
}

void bubbleSort(vector<Card> &a){
    bool flg = true;

    while(flg == true){
        flg = false;
        for(int i=a.size()-1; i>=1; i--){
            if(a[i-1].value > a[i].value){
                swap(a[i], a[i-1]);
                flg = true;
            }
        }
    }
}

void selectionSort(vector<Card> &a){

    for(int i=0; i<a.size()-1; i++){
        int minj = i;
        for(int j=i; j<a.size(); j++){
            if(a[minj].value > a[j].value) minj = j;
        }
        swap(a[i], a[minj]);
    }
}

bool isStable(vector<Card> &a, vector<Card> &b){
    for(int i=0; i<a.size(); i++){
        if(a[i].suit != b[i].suit) return false;
    }

    return true;
}

int main(){
    int N; cin >> N;
    vector<Card> a(N), b(N);
    for(int i=0; i<N; i++){
        cin >> a[i].suit >> a[i].value;
        b[i].suit = a[i].suit;
        b[i].value = a[i].value;
    }

    bubbleSort(a);
    selectionSort(b);

    print(a);
    cout << "Stable" << endl;

    print(b);
    if(isStable(a, b) == true) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
}


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);++i)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);--i)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld=long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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;
}

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
    ll n;
    cin>>n;
    Array p(n);
    REP(i,n) cin>>p[i];
    Array pp(n);
    REP(i,n) pp[p[i]-1]=i+1;
    Array a=pp,b=pp;
    REP(i,n-1) a[i+1]+=a[i];
    REP2(i,n-1) b[i]+=b[i+1];
    for(auto i:a) cout<<i<<" ";
    cout<<en;
    for(auto i:b) cout<<i<<" ";
    cout<<en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	solve();
	//ll t;cin>>t;REP(i,t) solve();

    return 0;
}

Measured memory_bytes: 1280
# ABC104B - AcCepted
def main():
    S = input().rstrip()
    flags = [S[0] == "A", S[2:-1].count("C") == 1, S.translate(str.maketrans({"A": None, "C": None})).islower()]
    print("AC" if all(flags) else "WA")


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    r1 = abs(candles[n]) + abs(candles[n+K-1]-candles[n])
    r2 = abs(candles[n+K-1]) + abs(candles[n]-candles[n+K-1])
    result.append(min(r1, r2))

print(min(result))


Measured memory_bytes: 14380
#include <stdio.h>

int main(void) {
  int i, j, k, n, ans[101], max = 0;
  for(i = 0; i < 101; ++i) ans[i] = 0;
  while(scanf("%d", &n) != EOF) {
    ++ans[n];
  }
  for(i = 1; i < 101; ++i) if(max < ans[i]) max = ans[i];
  for(i = 1; i < 101; ++i) if(ans[i] == max) printf("%d\n", i);
  return 0;
}


Measured memory_bytes: 2676
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
// 1 - (+) , 0 - (-)
const int MaxN = 1e5;
typedef long long LL;
using namespace std;
int a[MaxN + 5] , sum;
int pos = 0 , n;
LL ans = 0;
bool ok = 0;
void Init(){
	ok = 0;
	sum = ans = 0;
	for(int i = 1;i <= n;i++) 
		scanf("%d" , &a[i]);
}
void Solve(){
	ok = 0;
	for(int i = 1;i <= n;i++){
		if(ok){
			sum += a[i];
			if(sum >= 0) ans += sum + 1 , sum = -1;
			ok = 0;
		}
		else if(ok == 0){
			sum += a[i];
			if(sum <= 0) ans += abs(sum) + 1 , sum = 1;
			ok = 1;
		}
	}
	LL tmp = 0;
	ok = 1 , sum = 0;
	for(int i = 1;i <= n;i++){
		if(ok){
			sum += a[i];
			if(sum >= 0) tmp += sum + 1 , sum = -1;
			ok = 0;
		}			
		else if(ok == 0){
			sum += a[i];
			if(sum <= 0) tmp += abs(sum) + 1 , sum = 1;
			ok = 1;
		}
	}
	printf("%lld\n" , min(tmp , ans));
}
int main()
{
	while(~scanf("%d" , &n)){
		Init();
		Solve();
	}
}


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

class Main{
	public static void main(String[] args){
		solve();
	}
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		String[] s = new String[h];
		for(int i=0;i<h;i++){
			s[i] = sc.next();
		}
		int[] dx = {1,0,-1,0};
		int[] dy = {0,1,0,-1};
		boolean flag = true;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				boolean judge = true;
				if(s[i].charAt(j) == '#'){
					for(int k=0;k<4;k++){
						if(i+dx[k]<0 || i+dx[k]>=h){
							continue;
						}
						if(j+dy[k]<0 || j+dy[k]>=w){
							continue;
						}
						if(s[i+dx[k]].charAt(j+dy[k])=='#'){
							judge = false;
						}
					}
					if(judge){
						flag = false;
					}
				}
			}
		}
		if(flag){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");		
		}
	}
}


Measured memory_bytes: 21972
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <climits>

using namespace std;

const int N = 3e5 + 5000;
int n, m, T, a[N];
string s;
 
int main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	if ((s[2] == s[3]) && (s[4] == s[5])) cout << "Yes";
	else cout << "No";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL mod = 1000000007;

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

  LL N;string s;
  cin >> N >> s;

  LL flag = false;

  REP(j,4){
    //true->hituji false->ookami
    vector<bool> b(N + 2);
    b[0] = j %2 == 1;
    b[1] = j / 2 == 1;
    REP(i, N)
    {
      bool now = !(b[i] ^ b[i + 1] ^ (s[i!=0?i-1:N-1]== 'o'));
      //cout<<b[i]<<" "<<b[i+1]<<" "<<(s[i!=0?i-1:N-1]== 'o')<<" "<<now<<" "<<(s[i] == 'o')<<" "<<next<<endl;
      b[i + 2] = now;
    }
    if (b[0] == b[N] && b[1] == b[N+1]){
      flag = true;
      REP(k,N){
        cout << (!b[k+2] ? "S" : "W");
      }
      cout << endl;
      break;
    }
  }

  if(!flag){
    cout << -1 << endl;
  }
}


Measured memory_bytes: 592
#include<iostream>
#include<vector>
#include <unordered_map>  
#include <algorithm>
#include <functional>
#include <map>
using namespace std;


int main() {
	int n, a, b;
	cin >> n >> a >> b;

	std::vector<int> num = {};

	for (int i = 1; n >= i; ++i) {
		int keta[5];
		keta[4] = i / 10000;
		keta[3] = (i - keta[4] * 10000) / 1000;
		keta[2] = (i - keta[4] * 10000 - keta[3] * 1000) / 100;
		keta[1] = (i - keta[4] * 10000 - keta[3] * 1000 - keta[2] * 100) / 10;
		keta[0] = (i - keta[4] * 10000 - keta[3] * 1000 - keta[2] * 100 - keta[1] * 10);
		int wa = keta[4] + keta[3] + keta[2] + keta[1] + keta[0];
		if (a <= wa && wa <= b) {
			num.push_back(i);
		}
	}
	int sum = 0;
	for (auto tmp : num) {
		sum += tmp;
	}
	cout << sum << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int N, M;
char A[50][50], B[50][50];
bool F;

bool same(int y, int x){
	for(int i = 0; i < M; i++)
		for(int j = 0; j < M; j++)
			if(B[i][j] != A[y + i][x + j]) return false;
	return true;
}

int main(void){
	//IO("test.in", "test.out");
	scanf("%d%d", &N, &M), cin.get();
	F = false;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++) A[i][j] = cin.get();
		cin.get();
	}
	for(int i = 0; i < M; i++){
		for(int j = 0; j < M; j++) B[i][j] = cin.get();
		cin.get();
	}
	for(int i = 0; i < N - M + 1; i++)
		for(int j = 0; j < N - M + 1; j++)
			if(same(i, j)){
				F = true;
				break;
			}
	if(F) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n, m;
    cin >> n >> m;
    priority_queue<int> pq;
    rep(i, n) {
        int a;
        cin >> a;
        pq.push(a);
    }
    rep(i, m) {
        int a = pq.top();
        pq.pop();
        a /= 2;
        pq.push(a);
    }
    ll sum = 0;
    while(!pq.empty()) {
        sum += pq.top();
        pq.pop();
    }
    cout << sum << endl;
}

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



Measured memory_bytes: 3824
#include"bits/stdc++.h"
using namespace std;

#define MAX 5002

int n;
int A;
int B;

long long int dp[MAX][MAX];
bool us[MAX][MAX];


vector<int> v;


inline long long int dfs(int a, int b) {
	if (a == n) {
		return 0;
	}
	if (us[a][b])return dp[a][b];
	us[a][b] = true;
	dp[a][b] = LLONG_MAX;
	if (b == 0 || v[b - 1] < v[a]) {
		dp[a][b] = min(dp[a][b], dfs(a + 1, a + 1));
	}
	if (b == 0 || v[b - 1] < v[a]) {
		dp[a][b] = min(dp[a][b], dfs(a + 1, b) + A);
	}
	else {
		dp[a][b] = min(dp[a][b], dfs(a + 1, b) + B);
	}
	return dp[a][b];
}

int main() {
	cin >> n >> A >> B;
	for (int i = 0; i < n; i++) {
		int p;
		scanf("%d", &p);
		v.push_back(p);
	}
	printf("%lld\n", dfs(0, 0));
	return 0;
}


Measured memory_bytes: 220032
N = input()
n = int(N)
digit = len(N)

if digit == 1:
    print(n)
elif digit == 2:
    print(9)
elif digit == 3:
    print(9 + (n - 100 + 1))
elif digit == 4:
    print(909)
elif digit == 5:
    print(909 + (n - 10000 + 1))
else:
    print(90909)


Measured memory_bytes: 2940