akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 25;
const int di[] = {-1, 1, 0, 0};
const int dj[] = {0, 0, -1, 1};

int n, m;
char c[MAXN][MAXN];
bool used[MAXN][MAXN];
int dist[MAXN][MAXN];
queue < pair<int, int> > q;
int ans = 0;

int main() { 

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

  for (int si = 0; si < n; si++) {
    for (int sj = 0; sj < m; sj++) {
      if (c[si][sj] == '#') {
        continue;
      }
      memset(used, false, sizeof(used));
      memset(dist, 0, sizeof(dist));
      used[si][sj] = true;
      q.push({si, sj});
      while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
          int ci = p.first + di[k];
          int cj = p.second + dj[k];
          if (ci < 0 || ci >= n || cj < 0 || cj >= m || c[ci][cj] == '#' || used[ci][cj]) {
            continue;
          }
          used[ci][cj] = true;
          dist[ci][cj] = dist[p.first][p.second] + 1;
          q.push({ci, cj});
        }
      }
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          ans = max(ans, dist[i][j]);
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
n = int(input())
ans = 0
tmp = 0
prev = 0
for x, s in (map(int, input().split()) for _ in range(n)):
    dx = x - prev
    if dx > tmp:
        tmp = s
    else:
        tmp += s - dx
    ans = max(ans, tmp)
    prev = x
ans = max(ans, tmp)
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  int n=len(s);
  if(s[0]==s[n-1]){
    if(n%2==0) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
  }else{
    if(n%2==1) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
  }
}

Measured memory_bytes: 512
n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [10**10]*(n)
dp[0] = 0

for i in range(n):
    for j in range(1,k+1):
        if i+j <n:
            a = dp[i] + abs(h[i]-h[i+j])
            if a < dp[i+j]:
                dp[i+j] = a
        a = dp[i-2] + abs(h[i]-h[i-2])

print(dp[n-1])


Measured memory_bytes: 52704
#include <iostream>
#include <stack>
#include <map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <string.h>

using namespace std;

// NG

int N;

int main(int argc, char** argv) {
    cin >> N;
    if (N % 2 == 0)
        cout << N << endl;
    else
        cout << 2 * N << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
const ll inf = 1e18;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int n; cin >> n;
    ll mul = 1;
    vector<ll> a(100000);
    rep(i,n){
        cin >> a[i];
    }
    rep(i,n){
        if (a[i]==0){
            cout << 0 << endl;
            return 0;
        }
    }
    rep(i,n){
        if (inf / mul < a[i]){
            cout << -1 << endl;
            return 0;
        }
        mul *= a[i];
    }
    cout << mul << endl;
}

Measured memory_bytes: 3992
def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

import statistics
b = a.copy()
for i in range(n):
	b[i] = abs(a[i])

a1 = statistics.median(a)
a2 = statistics.median(b)

s = 0
s1 = 0
for i in range(n):
	s+=abs(a[i]-a1)
	s1+=abs(a[i]-a2)
s = min(s,s1)
print (int(s))	

Measured memory_bytes: 26176
use std::io;

fn main() {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).unwrap();
    
    let mut letter = buffer.trim().split_whitespace();
    let n = letter.next().unwrap().to_string().parse::<usize>().unwrap();
    let m = letter.next().unwrap().to_string().parse::<usize>().unwrap();

    let mut sub = vec!((0,0); n);
    for _ in 0..m {
        let mut res = String::new();
        io::stdin().read_line(&mut res).unwrap();
        
        let mut res = res.trim().split_whitespace();
        let num = res.next().unwrap().to_string().parse::<usize>().unwrap() - 1;
        let ans = res.next().unwrap().to_string();

        if &ans == "AC" {
            sub[num].0 += 1;
        } else if sub[num].0 == 0 {
            sub[num].1 += 1;
        }
    }
    
    let acc = sub.iter().filter(|&&(a, r)| a > 0).collect::<Vec<_>>().len();
    let pen: usize = sub.iter().map(|&(a, r)| if a > 0 { r } else { 0 }).sum();

    println!("{} {}", acc, pen);
}


Measured memory_bytes: 6396
#include <iostream>

using namespace std;
int p[110];
int main(){
    int i,j,x,n; cin >> x >> n;
    for(i=0;i<n;i++){
        cin >> p[i];
    }
    if(n==0){
        cout << x << endl;
        return 0;
    }
    int mn = 1000,ans = -1;
    for(i=0;i<=101;i++){
        for(j=0;j<n;j++){
            if(p[j]==i) break;
            if(j==n - 1){
                int dif = max(x - i,i - x);
                if(mn>dif){
                    ans = i; mn = dif;
                }
            }
        }
    }
    cout << ans << endl;
}

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

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

	int counter = 0;

	for (int i = 0; i <= A; ++i) {
		for (int j = 0; j <= B; ++j) {
			for (int k = 0; k <= C; ++k) {
				if (500 * i + 100 * j + 50 * k == X) counter++;
			}
		}
	}

	cout << counter << endl;

	return 0;
}

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

int main() {
  int b;
  string a;
  cin >>b>>a;

  int cr = 0;
  for (int i = 0; i < b; i++) {
    if (a.at(i) == 'R') {
      cr++;
    }
  }
  int cb = 0;
  for (int i = 0; i < b; i++) {
    if (a.at(i) == 'B') {
      cb++;
    }
}
 if(cr>cb){
  cout <<"Yes"<< endl;
}
 else{
cout<<"No"<<endl;
}
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

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

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}


const int INF = 1001001001;
const int MAX_N = 18;
int dp[1 << MAX_N][2 * MAX_N + 2];

vector<int> normalize(const vector<int> v) {
  const int N = v.size();
  vector<int> res(N);
  vector<pair<int,int> > t(N);
  REP(i, N) t[i] = { v[i], i };
  sort(ALL(t));
  int r = 0;
  REP(i, N) {
    r += (i > 0 && t[i - 1].first != t[i].first);
    res[t[i].second] = r;
  }
  return res;
}

int get(const vector<int>&A, const vector<int>& B, int pos, int c) {
  if ((pos - c) & 1) {
    return B[c];
  }
  return A[c];
}

int main2() {

  REP(i, 1<<MAX_N) REP(j, 2 * MAX_N + 2) dp[i][j + 1] = INF;

  int N = nextInt();

  vector<int> v(2 * N);
  REP(i, 2*N) v[i] = nextInt();
  v = normalize(v);

  vector<int> A(N);
  vector<int> B(N);
  REP(i, N) A[i] = v[i] + 1;
  REP(i, N) B[i] = v[N+i] + 1;

  // pv(ALL(A));
  // pv(ALL(B));

  dp[0][0] = 0;
  for (int s = 0; s < (1 << N); s++) {
    for (int l = 0; l <= 2*N; l++) {
      if (dp[s][l] >= INF/2) continue;
      // cout << s << " " << l << " " << dp[s][l] << endl;
      int pos = __builtin_popcount(s);
      REP(c, N) if ((s >> c & 1) == 0) {
        int f = get(A, B, pos, c);
        if (l > f) continue;
        int cost = 0;
        for (int i = c + 1; i < N; i++) if (s >> i & 1) cost++;
        // cout << "cost=" << cost << " , c=" << c  << " l=" << l << " f="<< f << endl;
        int ns = s | (1 << c);
        chmin(dp[ns][f], dp[s][l] + cost);
      }
    }
  }

  int ans = INF;
  REP(i, 2*N) {
    chmin(ans, dp[(1 << N) - 1][i+1]);
  }
  if (ans > INF / 2)
    cout << -1 << endl;
  else
    cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 39168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

ll gcd(ll x, ll y){
  return y ? gcd(y, x % y) : x; 
}

vector<pair<ll, int>> factorize(ll n){
  vector<pair<ll, int>> res;
  for(ll i = 2; i * i <= n; ++i){
    if(n % i) continue;
    res.emplace_back(i, 0);
    while(n % i == 0){
      n /= i;
      res.back().second++;
    }
  }
  if(n != 1) res.emplace_back(n, 1);
  return res;
}

int main(){
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a, b);
  auto f = factorize(g);
  cout << f.size() + 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <fstream>

#include <cmath>
#include <string>

#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

long arr[200000];
long dp[200000];

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

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

	arr[0] = 10000000;
	dp[0] = dp[1] = 0;
	for (int i = 2; i < n+1; i++) {
		dp[i] = dp[i-1] + abs(arr[i] - arr[i-1]);
		for (int j = i-1; (j > 0) && (j >= i-k); j--) {
			dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]));
		}
	}

	cout << dp[n] << endl;

	return 0;
}


Measured memory_bytes: 1792
import bisect
def inpl(): return list(map(int,input().split()))

N, Q = inpl()
A = sorted(inpl(), key=lambda x: -x)
if N % 2:
    N += 1
    A.append(0)

frogsum = [0] * N
cumsum = [0] * N
frogsum[0] = A[0]
frogsum[1] = A[1]
cumsum[0] = A[0]
cumsum[1] = A[0] + A[1]
for i in range(2,N-1):
    frogsum[i] = frogsum[i-2] + A[i]
    cumsum[i] = cumsum[i-1] + A[i]

biavg = [ -(A[i]+A[i*2])/2 for i in range(1,N//2) ]

def nsg(X):
    m = bisect.bisect_left(biavg, -X)
    if m < N//2-1 and biavg[m] == -X:
        m += 1

    return cumsum[m] + frogsum[N-2] - frogsum[m*2]


for _ in range(Q):
    X = int(input())
    print(nsg(X))

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

int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> heig(N);
  vector<int64_t> ans(N);
  ans.at(0) = 0;
  for(int i = 0;i < N;i++){
    cin >> heig.at(i);
  }
  for(int i = 0;i < N - 1;i++){
    if(heig.at(i) + ans.at(i) > heig.at(i+1)){
      ans.at(i+1) = heig.at(i) + ans.at(i) - heig.at(i+1);
    }
    else{
      ans.at(i+1) = 0;
    }
  }
  int64_t Ans;
  Ans = 0;
  for(int i = 0;i < N;i++){
    Ans = Ans + ans.at(i);
  }
  cout << Ans << endl;
}
  

Measured memory_bytes: 6420
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long int a,b,c,k;cin>>a>>b>>c>>k;
  if(k<=a)
  {
  	cout<<k;
  	return 0;
  }
  if(k<=(a+b))
  {
  	cout<<a;
  	return 0;
  }
  if(k<=(a+b+c))
  {
  	cout<<a+(k-a-b)*(-1);
  	return 0;
  }
  
}

Measured memory_bytes: 3580
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	var N int
	fmt.Scan(&N)
	var (
		ac_count  int = 0
		wa_count  int = 0
		tle_count int = 0
		re_count  int = 0
	)

	for i := 0; i < N; i++ {
		st := nextLine()
		switch st {
		case "AC":
			ac_count += 1
		case "WA":
			wa_count += 1
		case "TLE":
			tle_count += 1
		case "RE":
			re_count += 1
		}
	}

	fmt.Printf("AC x %d\n", ac_count)
	fmt.Printf("WA x %d\n", wa_count)
	fmt.Printf("TLE x %d\n", tle_count)
	fmt.Printf("RE x %d\n", re_count)
}


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

#define PB          push_back
#define PF          push_front
#define MP          make_pair
#define FI          first
#define SE          second
#define SIZE( A )   int( ( A ).size( ) )
#define ALL( A )    ( A ).begin( ), ( A ).end( )
#define ALLR( A )   ( A ).rbegin( ), ( A ).rend( )

using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef long double         lf;
typedef pair< int, int >    pii;
typedef pair< ll, ll >      pll;
typedef vector< bool >      vb;
typedef vector< lf >        vd;
typedef vector< ll >        vll;
typedef vector< int >       vi;
typedef vector< pii >       vpii;

const int MAXN = int( 2e5 );
const int MOD  = int( 360 );
const int oo   = INT_MAX;

ll a[ 7 ], b[ 7 ];

ll f( ) {
  memcpy( a, b, sizeof( ll )*7 );
  ll ans = a[ 1 ] + (a[ 0 ] - (a[ 0 ] & 1LL));
  if( (a[ 0 ] & 1LL) && a[ 3 ] && a[ 4 ] &&
     !( ((a[ 3 ] % 2LL) == 0) && ((a[ 4 ] % 2LL) == 0) ) ){
    ans += 3LL;
    --a[ 3 ];
    --a[ 4 ];
  }
  ans += a[ 3 ] - (a[ 3 ] & 1LL);
  ans += a[ 4 ] - (a[ 4 ] & 1LL);
  return ans;
}

ll g( ll mn ) {
  memcpy( a, b, sizeof( ll )*7 );
  ll ans = a[ 1 ];
  ans += mn*3LL;
  a[ 0 ] -= mn; a[ 3 ] -= mn; a[ 4 ] -= mn;
  ans += a[ 0 ]/2LL *2LL;
  ans += a[ 3 ]/2LL *2LL;
  ans += a[ 4 ]/2LL *2LL;
  return ans;
}

ll h( ) {
  memcpy( a, b, sizeof( ll )*7 );
  ll ans = a[ 1 ];
  ans += a[ 0 ]/2LL *2LL;
  ans += a[ 3 ]/2LL *2LL;
  ans += a[ 4 ]/2LL *2LL;
  if( a[ 0 ]%2LL == 1LL && a[ 3 ]%2LL == 1LL && a[ 4 ]%2LL == 1LL ) {
    ans += 3LL;
  }
  return ans;
}

int main( ) {

  #ifdef LOCAL
    freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
  #else
    //freopen( "attack.in", "r", stdin );
    //freopen( "attack.out", "w", stdout );
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );
  #endif

  for( int i = 0; i < 7; ++i ) cin >> b[ i ];

  ll mn = min( b[ 0 ], min( b[ 3 ], b[ 4 ] ) );

  ll ans = 0;
  for( int it = 0; it < 1000 && mn >= 0; it++, mn-- ) {
    ans = max( ans, g( mn ) );
  }

  cout << max( f( ), ans ) << '\n';
  return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    ll x2 = 0;
    rep(i, n) {
        if(i%2) x2 -= a[i];
        else x2 += a[i];
    }
    vector<int> ans(n);
    ans[0] = x2/2;
    rep(i, n-1) {
        ans[i+1] = a[i]-ans[i];
    }
    rep(i, n) ans[i] *= 2;
    rep(i, n) cout << ans[i] << endl;

    return 0;
}



Measured memory_bytes: 2048
#include <stdio.h>
 void main(){
     int N,a;
     scanf("%d",&N);
     a=N%10;
     if(a==3)
        printf("bon\n");
     else if(a==0||a==1||a==6||a==8)
        printf("pon\n");
     else
        printf("hon\n");
 }

Measured memory_bytes: 1588
#include<iostream>
using namespace std;
#define pi 3.14159265359
int main()
{
    unsigned long int n,m,a;
    unsigned long long int sum=0;
    cin>>n>>m;
    while(m>0){
        cin>>a;
        sum+=a;
        m--;
    }
    if(sum<=n) cout<<n-sum<<endl;
    else cout<<"-1"<<endl;
    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#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 all(in) in.begin(),in.end()
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
Def inf = sizeof(Def) == sizeof(long long) ?  2e18:1e9+10;
int main(){
	int T,te,pr,n;
	while(cin>>T>>te>>pr>>n,T){
		vvi wa(te,vi(pr));
		vector<pair<int,pii> >out(te);//team mis pr team
		rep(i,te)out[i].second.second=i;
		rep(i,n){
			int t,e,p,j;
			cin>>t>>e>>p>>j;
			if(j){
				wa[e-1][p-1]++;
			}else{
				out[e-1].second.first++;
				out[e-1].first+=20*wa[e-1][p-1]+t;
			}
		}
		sort(all(out),[](pair<int,pii>a,pair<int,pii>b){
			return a.second.first!=b.second.first?a.second.first>b.second.first:(a.first!=b.first?a.first<b.first:a.second.second>b.second.second);
		});
		rep(i,te){
			if(i){
				if(out[i-1].first-out[i].first==0&&out[i-1].second.first-out[i].second.first==0)cout<<"=";else cout<<",";
			}
			cout<<out[i].second.second+1;
			if(i==te-1)cout<<endl;
			
		}
	}
}


Measured memory_bytes: 3032
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;
typedef long long int64;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int64 n;
  cin>>n;

  if(n<=4){
    cout<<0<<endl;
    return 0;
  }

  if(n%2==0){
    int64 count=0;
    for(int64 div=10;div<=n;div*=5){
      count+=n/div;
    }
    cout<<count<<endl;
    return 0;
  }

  cout<<0<<endl;







  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>












template<class Ty>class bit
{
private: int n;
private: vector<Ty>tr;
public: void bldTr(int sz)
{
	n = sz;
	tr.resize(n + 10);
	for(int i = 1; i <= n; i++)tr[i] = 0;
}
public: Ty rd(int i)
{
	Ty sum = 0;
	while(i)
	{
		sum = sum + tr[i];
		i -= i&(-i);
	}
	return sum;
}

public: void updt(int i, Ty inc)
{
	while(i <= n)
	{
		tr[i] = tr[i] + inc;
		i += i&(-i);
	}
}
};







const int N = 2e5 + 10;
int n, k, crrnt, a[3][N];

bit<int>tr;




void solve()
{
	cin >> n >> k;
	crrnt = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[crrnt][i];
	}
	for(int i = 1; i <= k; i++)
	{
		tr.bldTr(n);
		for(int j = 1; j <= n; j++)
		{
			tr.updt(min(j + a[crrnt][j], n), 1);
			a[1 - crrnt][j] = tr.rd(n) - tr.rd(j - 1);
		}
		tr.bldTr(n);
		int c = 0;
		for(int j = n; j >= 1; j--)
		{
			a[1 - crrnt][j] += tr.rd(j);
			if(j > 1)tr.updt(max(j - a[crrnt][j], 1), 1);
			if(a[1 - crrnt][j] == n)c++;
		}
		crrnt = 1 - crrnt;
		if(c == n)break;
	}
	for(int i = 1; i <= n; i++)
	{
		cout << a[crrnt][i] << " ";
	}
	cout << "\n";
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt", "r", stdin);
#endif
	solve();
	return 0;
}

Measured memory_bytes: 5496
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll test,i,j=0,k,m;
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>k;
        if(k%2==0)
        {
            if(k%3==0 || k%5==0){}
            else j=1;
        }
    }
    if(j==1)cout<<"DENIED"<<endl;
    else cout<<"APPROVED"<<endl;
    return 0;
}


Measured memory_bytes: 256
using System;

class Program
{
  static void Main(string[] args)
  {
    string[] str = Console.ReadLine().Split(' ');
    
    int x = int.Parse(str[0]);
    int y = int.Parse(str[1]);
    int z = int.Parse(str[2]);
    
    Console.WriteLine("{0} {1} {2}",z,x,y);
  }
}

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

using namespace std;

const int maxn=110;

struct Node{
	int x,y;
};

Node r[maxn],b[maxn];

int vis[maxn];

int mp[maxn][maxn];

int n;

int girl[maxn];

bool find(int x){
	int i,j;
	for (j=1;j<=n;j++){    //??????
		if (mp[x][j]==true && vis[j]==false)      
		{
			vis[j]=1;
			if (girl[j]==0 || find(girl[j])) { 
				girl[j]=x;
				return true;
			}
		}
	}
	return false;
}

int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&r[i].x,&r[i].y);
	}
	for(int i=1;i<=n;i++){
		scanf("%d%d",&b[i].x,&b[i].y);
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(r[i].x<b[j].x&&r[i].y<b[j].y){
				mp[i][j]=1;
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));    //?????????
		if(find(i)) ans+=1;
	}
	printf("%d",ans);
	return 0;
} 

Measured memory_bytes: 256
import math
import heapq
import bisect
import numpy as np


h,w = map(int, input().split())
M = np.array([list(input().rstrip("\n")) for _ in range(h)]) == "."

D = np.zeros((h,w),dtype=int)
U = np.zeros((h,w),dtype=int)
L = np.zeros((h,w),dtype=int)
R = np.zeros((h,w),dtype=int)

for i in range(h):
    U[i] = (U[i-1] + 1) * M[i]
    D[-i-1] = (D[-i] + 1) * M[-i-1]

for i in range(w):
    L[:,i] = (L[:,i-1] + 1) * M[:,i]
    R[:,-i-1] = (R[:,-i] + 1) * M[:,-i-1]

print(np.max(U+D+L+R)-3)


Measured memory_bytes: 219472
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)
#D
def D():
    h,w,k = LI()
    dp = [[0 for i in range(w)] for j in range(h+1)]
    dp[0][0] = 1
    p = [1 for i in range(w+1)]
    for i in range(w):
        p[i+1] = p[i]*2
    l = [i for i in range(p[w-1])]
    i = 0
    while i < len(l):
        a = l[i]
        for j in range(w):
            if a&p[j] and a&p[j+1]:
                l.pop(i)
                i -= 1
                break
        i += 1
    for i in range(h):
        for j in range(w):
            a = 0
            b = 0
            c = 0
            for s in l:
                if 0 < j < w-1:
                    if p[j]&s:
                        c += 1
                    elif p[j-1]&s:
                        a += 1
                    else:
                        b += 1
                elif j == 0:
                    if p[j]&s:
                        c += 1
                    else:
                        b += 1
                else:
                    if p[j-1]&s:
                        a += 1
                    else:
                        b += 1
            dp[i+1][j] += b*dp[i][j]
            dp[i+1][j] %= mod
            if j > 0:
                dp[i+1][j-1] += a*dp[i][j]
                dp[i+1][j-1] %= mod
            if j < w-1:
                dp[i+1][j+1] += c*dp[i][j]
                dp[i+1][j+1] %= mod
    print(dp[h][k-1])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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


Measured memory_bytes: 42480
/**
 *    author:  tourist
 *    created: 25.12.2019 00:15:36       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> w(n), s(n), v(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> s[i] >> v[i];
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return w[i] + s[i] < w[j] + s[j];
  });
  vector<long long> dp(w[order.back()] + s[order.back()] + 1, 0);
  for (int i : order) {
    for (int j = s[i]; j >= 0; j--) {
      dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void){
    char a,b,c;
    scanf("%c %c %c", &a, &b, &c);
    if(a == 'S' && b == 'S' && c == 'S'){
        printf("0\n");
        return 0;
    }else if(a == 'S' && b == 'S' && c == 'R'){
        printf("1\n");
        return 0;
    }else if(a == 'S' && b == 'R' && c == 'S'){
        printf("1\n");
        return 0;
    }else if(a == 'R' && b == 'S' && c == 'S'){
        printf("1\n");
        return 0;
    }else if(a == 'R' && b == 'S' && c == 'R'){
        printf("1\n");
        return 0;
    }else if(a == 'R' && b == 'R' && c == 'S'){
        printf("2\n");
        return 0;
    }else if(a == 'S' && b == 'R' && c == 'R'){
        printf("2\n");
        return 0;
    }else if(a == 'R' && b == 'R' && c == 'R'){
        printf("3\n");
        return 0;
    }
    return 0;
}


Measured memory_bytes: 1612
#!/usr/bin/env python3
#ABC140 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
f = [0]*(n+1)
for i in range(n):
    f[p[i]] = i+1

ans = 0
l = [0] + [i for i in range(n+1)]
r = [i + 1 for i in range(n+1)] + [n+1]

#1-indexed
for i in range(1,n+1):
    #x:= p.index(i)
    x = f[i]
    
    #l1:= xの左にある1つ目のiよりも大きい数のindex
    #r1:= xの右にある1つ目のiよりも大きい数のindex
    l1,r1 = l[x],r[x]
    #l2:= xの左にある2つ目のiよりも大きい数のindex(= l1の左にある1つ目のiよりも大きい数のindex)
    #r2:= xの右にある2つ目のiよりも大きい数のindex(= r1の右にある1つ目のiよりも大きい数のindex)
    l2,r2 = l[l1],r[r1]
    #ans:= ans + (l1を含みr2を含まない場合 + r1を含みl2を含まない場合) * i
    ans += ((l1-l2)*(r1-x) + (x-l1)*(r2-r1))*i
    #r1の左にある1つ目のiよりも大きい数のindex = l1
    #l1の右にある1つ目のiよりも大きい数のindex = r1
    l[r1],r[l1] = l1,r1
print(ans)


Measured memory_bytes: 60432
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//�]���؂�グ�� =>  (a + b - 1) / b 

signed main(){
	int a,b,c,d; cin>>a>>b>>c>>d;
  cout<<(a-c)*(b-d)<<endl;
	
	return 0;
}

Measured memory_bytes: 3588
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	
	vector<int> hoge(200);
	int X, N;
	int mina = INF, ind = 0;
	
	cin>>X>>N;
	
	for(int i = 0; i < N; i++){
		int p;
		
		cin>>p;
		
		hoge[p] = true;
	}
	
	for(int i = 0; i < hoge.size(); i++){
		if(hoge[i]) continue;
		
		int ab = abs(i - X);
		
		if(ab < mina) {
			mina = ab;
			ind = i;
		}
	}
	
	cout<<ind<<endl;
	
	return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  string S;
  cin >> S;
  if((S[0] == S[1] && S[1] == S[2]) ||( S[1] == S[2] && S[2] == S[3])) cout << "Yes" <<endl;
  else cout << "No" <<endl;
} 


Measured memory_bytes: 3524
#include <bits/stdc++.h>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)

                    
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll mod = 1e9+7;
void chmod(ll &M){
  if(M >= mod) M %= mod;
  else if(M < 0){
     M += (abs(M)/mod + 1)*mod;
    M %= mod;
}
}
ll modpow(ll x, ll n){
   if(n==0) return 1;
  ll res=modpow(x, n/2);
 if(n%2==0) return res*res%mod;
else return res*res%mod*x%mod;
}
int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  else return GCD(b, a % b);
}

using namespace std;
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
int main()
{
    int N, M;
    cin >> N >> M;
    int sum_1 = 0;
    int sum_2 = 0;
    for(int i = 0; i < N; i++) { sum_1 += i; cerr << sum_1 << endl;}
    
    
    for(int j = 0; j < M; j++) { sum_2 += j; cerr << sum_2 << endl;}
    int ans = sum_1 + sum_2;
    cout << ans << endl;

}

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

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

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

    int max = v.at(0);

    string str = "Yes";
    for(int i=0; i<N-1; i++){
        if(max <= v.at(i+1)) max = v.at(i+1);
        else if(max-1 > v.at(i+1)) str = "No"; 
    }

    cout << str << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define gc getchar
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x1 uvuvwevwevwe
#define y1 onyetenyevwe
#define x2 ugwemubwem
#define y2 ossas
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
template <typename T> void scan(T &angka){
	angka=0;char input=gc();T kali=1;
	while(!(48<=input&&input<=57)){	if(input=='-')	kali=-1;input=gc();}
	while(48<=input&&input<=57)	angka=(angka<<3)+(angka<<1)+input-48,input=gc();angka*=kali;
}
template <typename T1,typename T2> void scan(T1 &angka1,T2 &angka2){
	scan(angka1);scan(angka2);
}
const LL INF=1000000000000;
const int MAXN=100;
int s,t,n,par[MAXN+5];
LL matriks[MAXN+5][MAXN+5]={},arr[MAXN+5],sum=0;
queue <int> cari;
vector <int> node[MAXN+5];
void inisbfs(){
	while(cari.size())
		cari.pop();
	for(int i=s;i<=t;i++)
		par[i]=-1;			//unvisited
}
bool bfs(){
	inisbfs();
	cari.push(s);
	par[s]=s;
	while(!cari.empty()&&par[t]==-1)
	{
		int u=cari.front();
		cari.pop();
		for(int v:node[u])
		{
			if(par[v]!=-1)
				continue;
			if(matriks[u][v]==0)
				continue;
			par[v]=u;
			cari.push(v);
		}
	}
	return (par[t]!=-1);
}
void balikpath(int now,LL &minflow){
	minflow=min(minflow,matriks[par[now]][now]);
	if(par[now]!=s)
		balikpath(par[now],minflow);
	
	matriks[par[now]][now]-=minflow;
	matriks[now][par[now]]+=minflow;
}
LL mincut(){
	LL ret=0;
	while(bfs())
	{
		LL minflow=INF;
		balikpath(t,minflow);
		//cout<<"mincut "<<minflow<<endl;
		ret+=minflow;
	}
	return ret;
}
void buatmatriks(){
	s=0;
	t=n+1;
	for(int i=1;i<=n;i++)
	{
		if(arr[i]>=0)
		{
			node[s].pb(i);
			node[i].pb(s);
			matriks[s][i]=abs(arr[i]);
		}
		else
		{
			node[i].pb(t);
			node[t].pb(i);
			matriks[i][t]=abs(arr[i]);
		}
		
		for(int j=i+i;j<=n&&arr[i]<0;j+=i)
		{
			if(arr[j]<0)
				continue;
			node[i].pb(j);
			node[j].pb(i);
			matriks[j][i]=INF;
		}
	}
	//cout<<"done"<<endl;
}
int main()
{
	scan(n);
	for(int i=1;i<=n;i++)
	{
		scan(arr[i]);
		sum+=max(0LL,arr[i]);
	}
	buatmatriks();
	cout<<sum-mincut()<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
using namespace std;
int main() {
  int W, H, x, y, r;
  cin >> W >> H >> x >> y >> r;
  if (x - r >= 0 && y - r >= 0 && x + r <= W && y + r <= H)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3084
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int main(void){
    int n,i,num,j,t,o;
    char line[9],line1[5];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&num);
        printf("Case %d:\n",i+1);
        for(o=0;j=0,memset(line1,'0',sizeof(line1)),memset(line,0,sizeof(line)),o<10;o++){
            num*=num;
            sprintf(line,"%d",num);
            while(line[j]) j++;
            j-=3;
            for(t=0;t<4 && j >= 0;j--,t++)
                line1[3-t]=line[j];
            line1[4]=0;
           printf("%d\n",num=atoi(line1));
        }
    }
    return 0;
}

Measured memory_bytes: 604
//
// Created by Mahmoud Rashad on 11/27/19.
//

#include <bits/stdc++.h>


using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<ii, ii>> vii;


int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;

    int n;
    cin >> n;
    vector<int> arr(n);
    int prev = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x - 1 >= prev) {
            prev = x - 1;
        } else if (x >= prev) {
            prev = x;
        } else {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 36
int main() {
	int i,j,n,min,flag=0;
	char C[N][3],x[3],data[N][3];
	scanf("%d", &n);
	for(i=0;i<n;i++) {
		scanf("%s",C[i]);
		strcpy(data[i],C[i]);
	}
    for(i=0;i<n-1;i++){
        for(j=n-1;j>0;j--){
	        if(atoi(&C[j][1])<atoi(&C[j-1][1])){
		        strcpy(x, C[j]);
	            strcpy(C[j],C[j-1]);
		        strcpy(C[j-1],x);
	        }
        }
    }
    for(i=0;i<n;i++){
	    printf("%s", C[i]);
	    if(i!=n-1)printf(" "); 
	}
	printf("\n");
	printf("Stable\n");
	for(i=0;i<n-1;i++) {
		min=i;
		for(j=i;j<n;j++) {
			if(atoi(&data[j][1])<atoi(&data[min][1])){
				min=j;
			}
		}
		strcpy(x,data[i]);
		strcpy(data[i],data[min]);
		strcpy(data[min],x);	
	}
	for(i=0;i<n;i++) {
		printf("%s", data[i]);
		if(strcmp(data[i],C[i])!=0)flag=1;
		if(i!=n-1)printf(" ");
	}
	printf("\n");
	if(flag==1)printf("Not stable\n");
	else printf("Stable\n");
}


Measured memory_bytes: 2140
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ll = long long;
#define MAX_N 1000001
#define MAX_M 100010
const long long mod = 1e9 + 7;
#define vec vector<int>
#define vecll vector<ll>
#define vecllvec vector<vector<ll>>
#define vecb vector<bool>
#define vecBvec vector<vector<bool>>
#define vecst vector<string>
#define veche vector<char>
#define vecd vector<double>
#define vecvec vector<vector<int>>
#define vecDvec vector<vector<double>>
#define vecHvec vector<vector<char>>
#define all(x) (x).begin(),(x).end()
#define ent cout<<endl
#define printvec(vec) for(int aqw=0;aqw<vec.size();aqw++){cout<<vec[aqw]<<" ";}ent;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,m,n) for(int i=m;i<(int)n;++i)
#define INF 1e+9
#define P pair<int, int>;
#define PLL pair<ll, ll>;
#define MAX_V 1000
#define PI 3.141592653589793
// cout << setprecision(15) << std::fixed;

int main()
{
	int n;
	cin >> n;
	vec A(n);
	bool q = true,e=true;
	int maxa = 0;
	int mai = 0;
	for (int i = 0;i < n;i++) {
		cin >> A[i];
		if (A[i] > 0) {
			e = false;
		}
		else {
			q = false;
		}
		if (abs(maxa) < abs(A[i])) {
			maxa = A[i];
			mai = i;
		}
	}
	int ans = 0;
	vec a, b;
	if (q && !(e)) {
		for (int i = 0;i < n - 1;i++) {
			ans++;
			A[i + 1] += A[i];
			a.push_back(i + 1);
			b.push_back(i + 1 + 1);
		}
	}
	else if(e && !(q)){
		for (int i = n-1;i>0;i--) {
			ans++;
			A[i-1] += A[i];
			a.push_back(i + 1);
			b.push_back(i - 1 + 1);
		}
	}
	else {
		for (int i = 0;i < n;i++) {
			ans++;
			A[i] += maxa;
			a.push_back(mai + 1);
			b.push_back(i + 1);
		}
		if (maxa < 0) {
			for (int i = n - 1;i > 0;i--) {
				ans++;
				A[i - 1] += A[i];
				a.push_back(i + 1);
				b.push_back(i - 1 + 1);
			}
		}
		else {
			for (int i = 0;i < n - 1;i++) {
				ans++;
				A[i + 1] += A[i];
				a.push_back(i + 1);
				b.push_back(i + 1 + 1);
			}
		}
	}
	cout << ans << endl;
	for (int i = 0;i < a.size();i++) {
		cout << a[i] << " " << b[i] << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <cmath>
using namespace std;
#define ll long long
#define endl '\n'
const int MAX = 2e5 + 4;
const int MOD = 1e9 + 7;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int a, b, m;
	cin >> a >> b >> m;
	vector<int> line(a), sline(b);
	int cheapest_refrigerator = 2e6+1, cheapest_microwave = 2e6+1;
	for (int i = 0; i < a; i++)
	{
		cin >> line[i];
		if (line[i] < cheapest_refrigerator)
			cheapest_refrigerator = line[i];
	}
	for (int i = 0; i < b; i++)
	{
		cin >> sline[i];
		if (sline[i] < cheapest_microwave)
			cheapest_microwave = sline[i];
	}
	int ans = cheapest_microwave + cheapest_refrigerator;
	for (int i = 0; i < m; i++)
	{
		int refrig, microwave, discount;
		cin >> refrig >> microwave >> discount;
		if (ans > line[refrig - 1] + sline[microwave - 1] - discount)
			ans = line[refrig - 1] + sline[microwave - 1] - discount;
	}
	cout << ans;
	return 0;
}

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

int main() {
	long long N, ANS = 0;
	cin >> N;
	vector<long long> H(N);
	for (int i = 0; i < N; i++) cin >> H[i];
	for (int i = 0; ; i++) {
		bool check = false, check2 = true;
		for (int j = 0; j < N; j++) {
			if (H[j] != 0) check = true, check2 = false, H[j]--;
			else {
				if (check) {
					ANS++;
					check = false;
				}
			}
		}
		if (check) ANS++;
		if (check2) break;
	}
	cout << ANS << endl;
}

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

int main()
{
    int n;
    cin >> n;
    if(n==1) cout << "Hello World" << endl;
    else{
        int a,b;
        cin >> a >> b;
        cout << a + b << endl;
    }
    return 0;
}

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

int main() {
	//入力
	int n;
	cin >> n;
	int a[100000];
	for (int i = 0; i < n; i++) cin >> a[i];

	//計算、出力
	int count = 0, s = 1;
	for (int i = 0; i < n; i++) {
		count++;
		s = a[s - 1];

		if (s == 2) {
			cout << count << endl;
			break;
		}
		if (count == n && s != 2) cout << -1 << endl;
	}

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>

using namespace std;


int main()
{
	long long A, B;
	cin >> A >> B;

	int N = 64;
	vector<long long> A_bits(N);
	vector<long long> B_bits(N);

	long long bit_n;
	long long c, d;
	for (int ni = 0; ni < N-1; ni++) {
		bit_n = (long long)pow(2, ni);

		c = A / (bit_n * 2);
		c *= bit_n;
		if ( (A / bit_n) % 2 == 0) {
			d = 0;
		}
		else {
			d = A % bit_n;
		}
		A_bits[ni] = c + d;

		c = B / (bit_n * 2);
		c *= bit_n;
		if ((B / bit_n) % 2 == 0) {
			d = 0;
		}
		else {
			d = B % bit_n + 1;
		}
		B_bits[ni] = c + d;
	}

	long long ans = 0;
	for (int ni = 0; ni < N-1; ni++) {
		if ((B_bits[ni] - A_bits[ni]) % 2 == 1) {
			ans += pow(2, ni);
		}
	}

	printf("%lld",ans);


	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

#define M 30000000

int dictionary[M]={0};
int four[13];

int trans(char ch)
{
	switch(ch)
	{
		case 'A': return 1;
		case 'C': return 2;
		case 'G': return 3;
		case 'T': return 4;
	}
}

void insert(char str[])
{
	long long key=0,s=0;
	int i;
	for(i=1;i<=strlen(str);i++)
	{
		key+=trans(str[ strlen(str)-i ])*four[i-1];
	}
	dictionary[key]=1;
}

int find(char str[])
{
	long long key=0,i;
	for(i=1;i<=strlen(str);i++)
	{
		key+=trans(str[ strlen(str)-i ])*four[i-1];
	}
	return dictionary[key]==1;
}

int main()
{
	int n,i,j;
	char com[9],str[14];
	four[0]=1;
	for(i=1;i<=12;i++)
	{
		four[i]=four[i-1]*4;
	}
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s %s",com,str);
		if(com[0]=='i')
		{
			insert(str);
		}
		else if(com[0]=='f')
		{
			if( find(str) ) printf("yes\n");
			else printf("no\n");
		}
	}
	return 0;
}


Measured memory_bytes: 8032
import java.util.*

fun main(args: Array<String>) {
    var result :Int = 0

    val n = readLine()!!

    for(moji in n){
        if(moji == 'A') result += 1
        else result -= 1
    }

    when (result){
        -3 -> print("No")
        3 -> print("No")
        else -> print("Yes")
    }

}

Measured memory_bytes: 33688
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextLong();
		int l = 0, r = 0;
		long ans = 0, sum = 0;
		while(l < n) {
			while(r < n && sum + a[r] == (sum^a[r])) {
				sum += a[r];
				r++;
			}
			ans += r - l;
			sum -= a[l];
			l++;
			if(l > r) r = l;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 86012
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
cout << fixed << setprecision(10);
ll n;
cin>>n;
double a[n]={};
double q=0;
for(ll i=0; i<n; i++){
cin>>a[i];}
sort(a,a+n);
q=(a[0]+a[1])/2;
for(ll i=2; i<n; i++){
q=(q+a[i])/2;}
cout<<q<<endl;}

Measured memory_bytes: 3704
n, m = map(int, input().split())
ps = [[i for i in input().split()] for i in range(m)]


correct = 0
penalty = 0
true_flag = [True] * (10 ** 5)
d = {}

for p, s in ps:
    p = int(p)

    # 初回でACのときはスルー
    if p not in d and s == 'AC':
        d[p] = 1
        correct += 1
        true_flag[p] = False
        # print('hoge1')
        # print(flag)
    # 2回目以降でACのときpenaltyを加算
    if true_flag[p]:
        if s == 'AC':
            penalty += d[p]
            correct += 1
            true_flag[p] = False
            # print('hoge2')
            # print(flag)
        # WAのときはdに追加していく
        else:
            if p not in d:
                d[p] = 1
                # print('hoge3')
                # print(flag)
            else:
                d[p] += 1
                # print('hoge4')
                # print(flag)

print(correct, penalty)


Measured memory_bytes: 38780
n,h=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b])
    
X.sort(key=lambda x:x[0],reverse=True)

Y=X[1:]
Y.sort(key=lambda x:x[1],reverse=True)

cnt=0

for i in range(n-1):
    if Y[i][1]>=X[0][1]:
        h-=Y[i][1]
        cnt+=1
        if h<=0:
            break

if h>0:
    h-=X[0][1]
    cnt+=1
    if h>0:
        for i in range(n-1):
            if Y[i][1]<X[0][1] and Y[i][1]>=X[0][0]:
                h-=Y[i][1]
                cnt+=1
                if h<=0:
                    break
        if h>0:
            if h%X[0][0]!=0:
                cnt+=h//X[0][0]+1
            else:
                cnt+=h//X[0][0]
print(cnt)

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

inline perm Unrank(int n, int r){
  perm p(n);
  for(int i=0;i<n;i++)p[i] = i;
  
  for(int i=n;i>0;i--){
    swap(p[i-1], p[r%i]);
    r /= i;
  }
  return p;
}

inline int Rank(perm p){
  int n = p.size();
  perm inv(n);
  for(int i=0;i<n;i++)inv[p[i]] = i;

  stack<int> s;
  for(int i=n;i>0;i--){
    s.push(p[i-1]);
    swap(p[i-1], p[inv[i-1]]);
    swap(inv[s.top()], inv[i-1]);
  }
  int r = 0;
  for(int i=1;i<=n;i++){
    r = s.top() + i * r;
    s.pop();
  }
  return r;
}

const int fact[] = {1,1,2,6,24,120,720,5040};
int dp[2][5040];
int n,d[110],a[110];

inline int cal(int pos, const perm &p){
  bool f = 0;
  int score = 0;
  rep(k,p.size()){
    if(p[k] == 0)f=1;
    else if(f && p[k]<=d[pos])score += a[pos];
    else if(!f && p[k]<=d[pos+p[k]])score += a[pos+p[k]];
  }
  return score;
}

inline perm red(perm p){
  p.erase(find(p.begin(),p.end(),0));
  rep(i,p.size())p[i]--;
  return p;
}

int main(){
  cin >> n;
  rep(i,n)cin >> d[i];
  rep(i,n)cin >> a[i];

  rep(i,n){
    int cur = i&1, nxt = 1-cur;
    int len = min(n-i, 7), nxtlen = min(n-i-1, 7);
    rep(j,fact[nxtlen])dp[nxt][j] = 0;

    rep(j,fact[len]){
      perm p = Unrank(len,j);
      
      if(len==nxtlen){
	perm np = p;
	np.push_back(p.size());
	int nxthash = Rank(red(np));
	dp[nxt][nxthash] = max(dp[nxt][nxthash], dp[cur][j]+cal(i,np));

	rep(k,len){
	  swap(np[len-k],np[len-1-k]);
	  int nxthash = Rank(red(np));
	  dp[nxt][nxthash] = max(dp[nxt][nxthash], dp[cur][j]+cal(i,np));
	}
      }else{
	int nxthash = Rank(red(p));
	dp[nxt][nxthash] = max(dp[nxt][nxthash], dp[cur][j]+cal(i,p));	
      }

    }
  }

  cout << dp[n&1][0] << endl;
}

Measured memory_bytes: 1268