akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int H,W,K;
  cin >> H >> W >> K;
  vector<vector<int>> S(H,vector<int>(0));
  for(int i=0;i<H;i++){
    string s;
    cin >> s;
    for(int j=0;j<W;j++){
      if(s[j]=='#') S[i].push_back(j);
    }
  }
  
  vector<vector<int>> ans(H,vector<int>(W,-1));
  int num = 0;
  for(int i=0;i<H;i++){
    if(S[i].size()==0){
      if(i==0) continue;
      if(ans[i-1][0]==-1) continue;
      for(int j=0;j<W;j++) ans[i][j] = ans[i-1][j];
    }
    else{
      int j=0;
      for(int k=0;k<S[i].size();k++){
        ++num;
        while(j<=S[i][k]){
          ans[i][j] = num;
          ++j;
        }
      }
      while(j<W){
        ans[i][j] = num;
        ++j;
      }
      
      if(i!=0){
        if(ans[i-1][0]==-1){
          for(int i2=0;i2<i;i2++){
            for(int j2=0;j2<W;j2++){
              ans[i2][j2] = ans[i][j2];
            }
          }
        }
      }
    }
  }
  
  for(int i=0;i<H;i++){
    cout << ans[i][0];
    for(int j=1;j<W;j++){
      cout << " " << ans[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
int min(int& a, int& b){return a<b?a:b;}
void pre_calc(int n, int k, vector<int>& V, vector<int>& dp){ 
    dp[0]=0;
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            int pos = i-j;
            if(pos<0)break;
            dp[i]=min(dp[i], dp[pos]+abs(V[i]-V[pos]));
        }
    }
}
int main(){
    int N, K;
    vector<int> V;
    vector<int> dp;
    cin>>N>>K;
    V.assign(N,0);
    dp.assign(N,INT32_MAX);
    for(int i=0;i<N;i++)cin>>V[i];
    pre_calc(N, K, V, dp);

    cout<<dp[N-1]<<endl;


    return 0;
}

Measured memory_bytes: 1024
A, B, C, K = map(int, input().split())

backup = K
AB = A + B
flag = False
ans = 0
if K <= A:
    print(K)
else:
    if A < K:
        K = K - A
        ans = ans + (A * 1)
    if B <= K:
        K = K - B
        flag = True
    if K > 0 and flag:
        ans = ans + (-1) * (backup - AB)
    print(ans)


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,n=1,m=0,p;
  cin >> N;
  for (int i = 2; i <= N; i++) {
    p = 0;
    for (int j = i; !(j%2); j /= 2, p++);
    if (p > m) {
      m = p;
      n = i;
    }
  }
  cout << n;
}

Measured memory_bytes: 3588
#include <iostream>
#include <string>

typedef long long ll;

std::string alphabet = "abcdefghijklmnopqrstuvwxyz";
ll N;

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

  std::cin >> N;
  std::string ans = "";
  while (N) {
    N--;
    ans = alphabet[N % 26] + ans;
    N /= 26;
  }

  std::cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
//orz jzm
#define ll long long
#define ull unsigned ll
const ll PR=19260817;
const int N=200005;
struct DSU {
	int fa[N];
	void init(int sz) {
		for (int i=0; i<sz; i++) {
			fa[i]=i;
		}
	}
	int Find(int x) {
		return fa[x]==x?x:fa[x]=Find(fa[x]);
	}
	void Union(int x, int y) {
		x=Find(x), y=Find(y);
		if (x!=y)
			fa[x]=y;
	}
};
int n;
DSU d1, d2;
map<pair<int, int>, int> ans;
int main() {
	scanf("%d", &n);
	int m1, m2;
	scanf("%d%d", &m1, &m2);
	d1.init(n);
	while (m1--) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		d1.Union(u, v);
	}
	d2.init(n);
	while (m2--) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		d2.Union(u, v);
	}
	for (int i=0; i<n; i++) {
		ans[make_pair(d1.Find(i), d2.Find(i))]++;
	}
	for (int i=0; i<n; i++) {
		printf("%d ", ans[make_pair(d1.Find(i), d2.Find(i))]);
	}
	return 0;
}

Measured memory_bytes: 13568
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = 10**20
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    x = X[x1] - X[x0]
    Y_s = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Y_s) - K + 1):
      y = Y_s[y0 + K - 1] - Y_s[y0]
      r = min(r, x * y)
print(r)

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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	int64_t A, B, C, K;

	cin >> A >> B >> C >> K;
	if (K <= A + B)
		cout << min(A, K) << endl;
	else
		cout << A + A + B - K << endl;
	return 0;
}


Measured memory_bytes: 3616
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 21 13:58:43 2020

@author: 藤原聖士
"""

"""
N=int(input())
A=int(input())
B=int(input())
"""

N,A,B=map(int,input().split())

check=0
checks=0
count=0

for i in range(N):
    checks=0
    Ns=i+1
    while True:
        
        check=Ns%10
        checks+=check
        Ns=int(Ns/10)

        if Ns==0:
            break
    if checks>= A and checks<=B:
        count+=i+1
        #print(i)

print(count)

Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a > b && a > c) {
        if (a == b + c) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    } else if (b > c && b > a) {
        if (b == c + a) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    } else if (c > b && c > a) {
        if (c == a + b) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    } else {
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();

        if (a >= 3200) {
            System.out.print(s);
        } else {
            System.out.print("red");
        }
    }
}

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

int main() {
    int N;
    int a, b, c, d;

    cin >> N;

    a = N / 1000;
    b = N % 1000 / 100;
    c = N % 1000 % 100 / 10;
    d = N % 1000 % 100 % 10;

    bool ABC, ACD, BCD, ABD;

    ABC = (a == b) && (b == c);
//    ACD = (a == c) && (c == d);
    BCD = (b == c) && (c == d);
//    ABD = (a == b) && (b == d);

//    if(ABC || ACD || BCD || ABD){
    if(ABC || BCD){
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

vi od,all;

void solve(int n){
	vi dp(n+1,INF);
	ll odans=0;
	dp[0]=0;
	rrep(i,od.size()){
		rep(j,n){
			if(dp[j]==INF)continue;
			if(j+od[i]>n)j=n;
			else chmin(dp[j+od[i]],dp[j]+1);
		}
	}
	odans=dp[n];
	rrep(i,all.size()){
		rep(j,n){
			if(dp[j]==INF)continue;
			if(j+all[i]>n)j=n;
			else chmin(dp[j+all[i]],dp[j]+1);
		}
	}
	puta(dp[n],odans);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	for(int i=1;(i)*(i+1)*(i+2)/6<=1E6;i++){
		if((i)*(i+1)*(i+2)/6%2==1)od.push_back((i)*(i+1)*(i+2)/6);
		else all.push_back((i)*(i+1)*(i+2)/6);
	}
	while(cin>>n,n)solve(n);
}



Measured memory_bytes: 6824
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int main(void){
    int k, s;
    scanf("%d%d", &k, &s);
    int cnt = 0;
    int a, b;

    for (a = 0; a <= k;a++){
        for (b = 0; b <= k;b++){
            if (k >= s - (a + b)&& s-(a+b)>=0)
                cnt++;
            }
        }
    printf("%d", cnt);

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
    int N,K;
    string S;
    cin >> N >>S >>K;
    
    for (int i=0; i<N; i++) {
        if (S[i]!=S[K-1]) {
            S[i]='*';
        }
    }
    cout << S << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//typedef pair<ll,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}

int main() {
    string s;
    cin>>s;
    int cnt=0,tmp=0;
    for(int i=0;i<s.length();i++){
      if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T') tmp++;
      else {
        cnt=max(cnt,tmp);
        tmp=0;
      }
    }
    cnt=max(cnt,tmp);
    cout<<cnt;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    int d[N];
    for(int i=0;i<N;i++){
        cin >> d[i];
    }
    int ans=0;
    for(int i=0;i<N;i++){
        for(int j=i;j<N-1;j++){
            ans += d[i]*d[j+1];
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(R: int, G: int):
    print(G*2-R)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    R = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    solve(R, G)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <queue>
#include <bitset>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll right(vector<P>& r, int l){
    priority_queue<int> q;
    ll sum=0;
    int num=0;
    for(int i=l+1, sz=r.size()+l; i<=sz; ++i){
        while(i>r[num].first && num<r.size()){
            q.push(r[num].second);
            ++num;
        }
        if(!q.empty()) {
            sum += q.top(); 
            q.pop();
        }
    }
    return sum;
}

ll left(vector<P>& l){
    priority_queue<int> q;
    ll sum=0;
    int num=0;
    for(int i=l.size(); i>0; --i){
        while(i<=l[num].first && num<l.size()){
            q.push(l[num].second);
            ++num;
        }
        if(!q.empty()){
            sum += q.top();
            q.pop();
        }
    }
    return sum;
}

void solve()
{
    int n;
    cin >> n;
    vector<P> r, l;
    r.reserve(n); l.reserve(n);

    ll base=0;
    rep(i,n){
        int K,R,L;
        cin >> K >> L >> R;
        if(L>R){
            l.emplace_back(K,L-R);
            base += R;
        }
        else{
            r.emplace_back(K,R-L);
            base += L;
        }
    }
    sort(l.rbegin(),l.rend());
    sort(r.begin(),r.end());
    cout << base+left(l)+right(r,l.size()) << endl;
    return;
}

int main(){
    int T;
    cin >> T;
    rep(i,T) solve();
    return 0;
}


Measured memory_bytes: 5512
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
static const int INF = 1e9+7;
// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i =a; i < b; i++)
#define all(a) a.begin(), a.end()
#define PI 3.14159265359

int main(){
    ll n, k; cin >> n >> k;
    cout << k * int(pow(k - 1, n - 1)) << endl;

    return 0;
}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int n ;
  double t , a ;
  cin >> n >> t >> a ;
  double MIN = 1e9;
  int ans = 1;
  
  rep(i,n){
    double x ;
    cin >> x ;
    if(MIN > abs(a-(t-x*0.006))){
      MIN = min(abs(a-(t-x*0.006)), MIN);
      ans = i+1 ;
    }
  }
    cout <<ans ;
    


}


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

int main(){
  int n,k;
  cin >> n >> k;
  int t = 1;
  for (int i=0;i<n;i++){
    int a = t * 2;
    int b = t + k;
    t = min(a,b);
  }
  cout << t << endl;
  return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n,d;

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

  cin>>n>>d;
  ll g=0;
  rep(i,n){
    ll a;
    cin>>a;
    a--;
    g^=(a%(d+1));
  }
  if(g==0)cout<<"Second"<<endl;
  else cout<<"First"<<endl;

  return 0;
}



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

using namespace std;

#define ll long long
#define pi pair<int, int>
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int mxn = 1e6 + 5;
const ll MOD =  1e9 + 7;
int arr[mxn];
int n, m, k, q;
string s, t;

void solve(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] > arr[k] && (arr[i] != arr[j] && arr[j] != arr[k])) ans++;
            }
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}


Measured memory_bytes: 3580
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;

const int V = 3000;
int main() {
    int P; cin >> P;
    using mint = ll;
    vector< vector<mint> > table(V, vector<mint>(V));
    table[0][0] = mint(1);
    for(int i=1; i<V; i++) {
        table[i][0] = mint(1);
        for(int j=1; j<=i; j++) {
            table[i][j] = table[i-1][j-1] + table[i-1][j];
            if(table[i][j] >= P) table[i][j] -= P;
        }
    }

    vector<mint> A(P);
    for(int i=0; i<P; i++) {
        cin >> A[i];
    }

    vector< vector<mint> > pows(P, vector<mint>(P));
    for(int i=0; i<P; i++) {
        pows[i][0] = mint(1);
        for(int j=1; j<P; j++) {
            pows[i][j] = pows[i][j-1] * mint(i);
            pows[i][j] %= P;
        }
    }

    vector<mint> B(P);
    for(int i=0; i<P; i++) {
        B[0] += A[i];
        if(B[0] >= P) B[0] -= P;
        for(int k=0; k<P; k++) {
            mint coeff = A[i] * table[P - 1][k] % P * pows[i][P-1-k] % P;
            if(k % 2 == 0) coeff = P - coeff;
            B[k] += coeff;
            if(B[k] >= P) B[k] -= P;
        }
    }

    for(int i=0; i<P; i++) {
        cout << B[i] << " \n"[i + 1 == P];
    }
    return 0;
}


Measured memory_bytes: 141056
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

#define int ll
#define REP(i,e,s) for(register int i=(e); i<=(s); i++)
#define DREP(i,e,s) for(register int i=(e); i>=(s); i--)
#define ll long long
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define lowbit(x) x&(-x)
int read() {
	int x=0,f=1,ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=100000+10;

int a[MAXN],sum[MAXN];
struct bitree {
	int c[MAXN],n;
	void add(int x,int d) {
		while(x<=n) {
			c[x]+=d;
			x+=lowbit(x);
		}
	}
	int ask(int x) {
		int ans=0;
		while(x) {
			ans+=c[x];
			x-=lowbit(x);
		}
		return ans;
	}
} s;

int n;

int b[MAXN];

bool check(int mid) {
	sum[0]=0;s.n=0;
	memset(s.c,0,sizeof(s.c));
	REP(i,1,n) sum[i]=(a[i]<=mid?-1:1);
	REP(i,1,n) sum[i]+=sum[i-1];
	REP(i,0,n) b[++s.n]=sum[i];
	sort(b+1,b+s.n+1);
	s.n=unique(b+1,b+s.n+1)-b-1;
	REP(i,0,n) sum[i]=lower_bound(b+1,b+s.n+1,sum[i])-b;
	long long ans=0; 
	REP(i,0,n) ans += s.ask(sum[i]),s.add(sum[i],1);
	return ans*2>=1ll*n*(n+1)/2;
}
signed main() {
	n=read();s.n=n;
	REP(i,1,n) a[i]=read();

	int l=1,r=1e9,ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1,ans=mid;
	}

	printf("%lld\n",ans);
	return 0;
}



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

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()
 
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  bool field[12][12] = {};
  string s;
  while(cin >> s) {
    rep(i, 8) {
      field[0][i] = s[i] == '1';
    }
    loop(i, 1, 8) {
      cin >> s;
      loop(j, 0, 8) {
        field[i][j] = s[j] == '1';
      }
    }
   
    char ans = '.';
    rep(i, 8) {
      rep(j, 8) {
        if(field[i][j]) {
          if(field[i][j+1] && field[i+1][j] && field[i+1][j+1]) ans = 'A';
          else if(field[i+1][j] && field[i+2][j] && field[i+3][j]) ans = 'B';
          else if(field[i][j+1] && field[i][j+2] && field[i][j+3]) ans = 'C';
          else if(field[i][j+1] && field[i+1][j+1] && field[i+1][j+2]) ans = 'E';
          else if(field[i+1][j] && field[i+1][j+1] && field[i+2][j+1]) ans = 'F';
          else if(field[i+1][j] && field[i+1][j-1] && field[i+2][j-1]) ans = 'D';
          else ans = 'G';
          break;
        }
      }
      if(ans != '.') break;
    }
    cout << ans << endl;
    getline(cin, s);
  }
}

Measured memory_bytes: 1180
N = int(input())
S = input()
D = [0]*(N+1)
for i in range(N):
    D[i+1] = D[i] + (S[i] == '#')
ans = 10**18
for i in range(N+1):
    ans = min(ans, D[i] + (N-i - (D[N] - D[i])))
print(ans)

Measured memory_bytes: 42608
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(f) printf("%.10lf\n",f)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
int main(void){
  int m,d,cnt=0;
  scanf("%d %d",&m,&d);
  for(int i=4;i<=m;i++){
    for(int j=22;j<=d;j++){
      if(j%10<2)continue;
      if((j/10)*(j%10)==i){
        cnt++;
      }
    }
  }
  PRN(cnt);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define LL long long
#define Accel ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define Re(a,b) memset(a,b,sizeof a)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define ALL(X) (X).begin(), (X).end()
#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
#define REP(I, N) for (int I = 0; I < (N); I++)
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define SZ(a) ((int)a.size())
//#pragma GCC optimize(2)
using namespace std;
//const double eps=1e-6;
//typedef complex<double>C;
//const double PI(acos(-1.0));
//for(int mask=i;mask>0;mask=(mask-1)&i)
//int a[25]= { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
//__gcd, atan2(y,x)=y/x , __int128
//c(n,k)=c(n-1,k-1)+c(n-1,k)
//c(i,r),i for r to n =c(n+1,r+1)
//void add(int x){while(x<N)BIT[x]++,x+=x&-x;}
//int sum(int x){int s=0;while(x){s+=BIT[x];x-=x&-x;}return s;}
//int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
//LL pw(LL a,LL b){LL t=1;for(;b;b>>=1,a=a*a%M)b&1?t=t*a%M:0;return t;}
//log() = ln() , log(x)/log(y)=log(y)-base-x
//INT_MAX 127,INT_MIN 128
//isalnum() decimal digit or an uppercase or lowercase letter
//int dw[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//int dw[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
//cout<<fixed<<setprecision(12)<<ans<<endl;
//__builtin_popcount(mask)
LL a,b,c,x,y;
int main() {
	cin>>a>>b>>c>>x>>y;
	LL tot=0;
	if(c*2<a+b){
		LL t=min(x,y);
		tot+=t*c*2;
		x-=t,y-=t;
	}
	if(x>0&&c*2<a){
		tot+=c*2*x;
	}
	else if(y>0&&c*2<b){
		tot+=c*2*y;
	}
	else tot+=x*a+y*b;
	cout<<tot<<endl;
}

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

int A[100010];
int X[100010];
int main(void) {

    long long int N,K,Q;
    cin >> N >> K >> Q;

    for(int i=0; i<N; i++)
    {
        X[i] = 0;
    }

    for(int i=0; i<Q; i++)
    {
        cin >> A[i];
        X[A[i]-1]++;
    }

    for(int i=0; i<N; i++)
    {
        if (K + X[i] - Q > 0)
          cout << "Yes" << endl;
      else 
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 1408
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (1 ? 1e9 + 7 : 998244353);



int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	ll a, b, c, d, e, f, g, T;
	string z;
	cin >> z;
	a = z.size();
	for (int i = 0; i < a - 1; i++)
	{
		if (z[i] == z[i + 1])
		{
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
}

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

int main() {
	string S;
	long long NOW = 1, MOD = 1000000007;
	static long long DP[100010][13] = {};
	DP[0][0] = 1;
	cin >> S;
	reverse(S.begin(), S.end());
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '?') {
			for (int j = 0; j < 13; j++) {
				for (int k = 0; k < 10; k++) {
					DP[i + 1][(j + NOW * k) % 13] += DP[i][j];
					DP[i + 1][(j + NOW * k) % 13] %= MOD;
				}
			}
		}
		else {
			for (int j = 0; j < 13; j++) {
				DP[i + 1][(j + NOW * (S[i] - '0')) % 13] = DP[i][j];
			}
		}
		NOW = (NOW * 10) % 13;
	}
	cout << DP[S.size()][5] << endl;
}

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

using namespace std ;

int main() {

    long long int n ,ans=0 ,i ,c=0;

    string s , ss ,sss ;

    cin >> n ;
    cin >> s >> ss >> sss ;

    for(i=0;i<n;i++){
          //  cout << i<<" " <<ans<< " " <<c <<endl;


        if(s[i]==ss[i]){
            c++ ;
         //   cout<<"ok1";
         }
        if(s[i]==sss[i])
            {c++ ;
           // cout<< "ok2" ;
            }
        if(ss[i]==sss[i])
           {

            c++ ;
          //  cout<< "ok3" ;
            }
        if(c==0)
            ans+=2 ;
        else if(c==1)
            ans+=1;


        //    cout << i<<" " <<ans<< " " <<c <<endl;

        c=0 ;

    }





    cout <<ans<<endl ;



    return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
P=list(map(int,input().split()))
# Ary=[(p+1)/2 for p in P]

Ary=[]
x=0
for p in P:
    x+=(p+1)/2
    Ary.append(x)
# print(Ary)
ans=Ary[K-1]
buf,left,right=0,0,0
for i in range(1,N-K+1):
    left,right=i,left+K
    # print(left,right)
    buf=Ary[right]-Ary[left-1]
    if buf>ans:
        ans=buf
print(ans)

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<string>>PS(M, vector<string>(2));
  
  for(int i=0; i<M; i++)cin >> PS.at(i).at(0) >> PS.at(i).at(1);
  
  int AC=0; int WA=0;int P;
  vector<int>F(N, 1);
  vector<int>count(N);
  for(int i=0; i<M; i++){
    P = stoi(PS.at(i).at(0))-1;
    if(F.at(P)){
      if(PS.at(i).at(1)=="WA")count.at(P)++;
      else{
        AC++;
        WA += count.at(P);
        F.at(P)=0;
      }
    }
  }
    
    cout << AC << " " << WA << endl;
}

Measured memory_bytes: 14260
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

const int MAXN = 1000010;

vector<int> g[MAXN];
bool is[MAXN];

int ret = 0, k;

int dfs(int v) {
	int depth = 1;
	FOR (i, g[v].sz) {
		depth = max(depth, 1 + dfs(g[v][i]));
		if (!is[v] && depth == k) {
			ret++;
			depth = 0;
			ffor (j, i + 1, g[v].sz)
				dfs(g[v][j]);
			break;
		}
	}
	return depth;
}

int main() {
	int n;
	cin >> n >> k;
	SET(is, 0);
	FOR (i, n) {
		int a;
		cin >> a;
		a--;
		if (!i) {
			if (a)
				ret++;
		}
		else {
			g[a].pb(i);
			if (!a)
				is[i] = true;
		}
	}
	is[0] = true;
	if (k == 1)
		ret += n - 1 - (signed int)g[0].sz;
	else
		dfs(0);
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 34048
'use strict';

function main(stdin) {
  const input = stdin.split('\n');
  const N = Number(input.shift());
  const W = input[0].split(' ').map(v => parseInt(v, 10));

  let S2 = W.reduce((a, b) => a + b);
  let S1 = 0;
  const diff = [];

  for (let T = 0; T < N - 1; ++T) {
    S1 += W[T];
    S2 -= W[T];
    diff[T] = Math.abs(S1 - S2);
  }

  const min = diff.reduce((a, b) => Math.min(a, b));
  
  console.log(min);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 11468
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n, k; cin>>n>>k;
    vl ps(n); cin>>ps;

    priority_queue<ll> rq;
    priority_queue<ll, vl, greater<ll>> lq;
    map<ll, ll> lcnt, rcnt;
    ll ans = 1;
    ll c = 1;
    bool org = false;
    rep(i, n) {
        if (i > 0 && ps[i - 1] < ps[i]) c++;
        else c = 1;

        if (i < k) {
            lq.push(ps[i]);
            rq.push(ps[i]);
            continue;
        }

        bool f = true;
        
        while (lcnt[lq.top()]) {
            lcnt[lq.top()]--;
            lq.pop();
        }
        if (ps[i - k] != lq.top()) {
            lcnt[ps[i - k]]++;
            f = false;
        }
        else lq.pop();
        lq.push(ps[i]);

        while (rcnt[rq.top()]) {
            rcnt[rq.top()]--;
            rq.pop();
        }
        if (ps[i - k] != rq.top()) {
            rcnt[ps[i - k]]++;
        }
        else rq.pop();
        rq.push(ps[i]);
        if (rq.top() != ps[i]) f = false;

        if (c >= k) {
            if (org) continue;
            org = true;
        }

        if (!f) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 29792
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,k = get_nums_l()

check = [False] * (n+1)

for i in range(k):
    d = int(input())
    for a in get_nums_l():
        check[a] = True

ans = 0

for i,b in enumerate(check):
    if not b:
        ans += 1

print(ans-1)


Measured memory_bytes: 68524
#include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define ld long double
    #define MOD 1000000007
    #define mod9 1000000009
    #define fast ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    #define mp make_pair
    #define pb push_back
    #define ct ll t;cin>>t;while(t--)
    #define bi begin()
    #define ei end()
    #define fi first 
    #define se second  
    #define foe(i,a,b) for(ll i=a;i<b;i++)
    #define rfoe(i,a,b) for(ll i=a;i>=0;i--)
    #define sz(s) s.size() 
    #define mem(a,s) memset(a,s,sizeof(a)) 
    #define all(v) v.bi,v.ei
    #define MAX             8000000000000000064LL
    #define MIN            -8000000000000000064LL   

    typedef pair<ll,ll> pii;
    
    ll add(ll a, ll b){return (a%MOD + b%MOD + ((MAX)/MOD)*MOD)%MOD;}
    ll sub(ll a, ll b){return (a%MOD - b%MOD + ((MAX)/MOD)*MOD)%MOD;}
    ll mul(ll a, ll b){return ((a%MOD)*(b%MOD) + ((MAX)/MOD)*MOD)%MOD;}
    ll lcm(ll a,ll b){return(a*b)/__gcd(a,b);}
    ll fact[1000007 ]={0};
    ll expo(ll x, ll y) {ll res=1;x=x%MOD;while(y>0){if(y&1)res=(1ll*res*x)%MOD;
    y=y>>1;x=(1ll*x*x)%MOD;} return res;}
    void facto() {fact[0]=1;fact[1]=1;for(ll i=2;i<1000007;i++)fact[i]=(fact[i-1]*i)%MOD;}
    ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expo(fact[r],MOD-2)))%MOD; res=(res*(expo(fact[n-r],MOD-2)))%MOD; return res;}
    ll npr(ll n,ll r) {facto(); ll res=1; res=fact[n]; res=(res*(expo(fact[n-r],MOD-2)))%MOD; return res; }
    int const N=2e5+9;
    ll const INF = 2e18+5;
    ll dx[8]={0,0,1,-1,1,1,-1,-1};
    ll dy[8]={1,-1,0,0,-1,1,-1,1};
    long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = mul(res,a);
        a = mul(a,a);
        b >>= 1;
    }
    return res;
}
  
    void solve()
    {  
        ll n;
        cin>>n;
        ll t=0;
        ll x[n],y[n];
        foe(i,0,n)
        {
            cin>>x[i]>>y[i];
        }
        foe(i,0,n)
        {
            if(x[i]==y[i])
            {
                t++;
            }
            else
            {
                t=0;
            }
            
            if(t==3)
            {
                cout<<"Yes\n";
                return;
            }
            
        }
        cout<<"No\n";
    }
    int main()
    {
        fast
        // facto();
        // Sieve();
    //    ct    
        { 
            solve();
        }
    }


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll x,n=100;int i=1;scanf("%lld",&x);
	for(i=1;i<=4000;++i)
	{
		n*=1.01;
		if(n>=x) break;
	}
	
	printf("%d",i);
} 

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

int main(void){
    int h,w;
    cin >> h >> w;
    int a[h+2][w+2];
    char c[h][w];
    
    for(int i = 0;i < h+2;i++){
        for(int j = 0;j < w+2;j++){
            a[i][j] = 0;
        }
    }
    
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            cin >> c[i][j];
            if(c[i][j] == '#'){
                for(int p = i-1;p < i+2;p++){
                    for(int q = j-1;q < j+2;q++)a[p+1][q+1]++;
                }
            }
        }
    }
    for(int H = 0,b = 0;H < h+2;H++,b = 0){
        for(int W = 0;W < w+2;W++){
            if((1 <= H && H <= h)&&(1 <= W && W <= w)){
                b++;
                if(c[H-1][W-1] == '#')cout << "#";
                else cout << a[H][W];
            }
        }
        if(b != 0)cout << endl;
    }
}


Measured memory_bytes: 256
N = int(input())
t_pre, x_pre, y_pre = 0, 0, 0
flag = True
for i in range(N):
    t, x, y = map(int, input().split())
    delta_t = t - t_pre
    delta_x = abs(x - x_pre)
    delta_y = abs(y - y_pre)
    if t % 2 != (x + y) %2:
        flag = False
        break
    if delta_x + delta_y > delta_t:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')

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

int main(void) {
    int a, b, c;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a >> b >> c;
    cout << (a == b + c || b == c + a || c == a + b? "Yes" : "No") << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>

using namespace std;

int main(void) {
	int d, n;
	cin >> d >> n;
	int p = pow(100, d);
	if (n == 100) {
			cout << p * (n + 1);
	}
	else {
		cout << p * n;
	}
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())





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

	string s;
	int q;
	cin >> s >> q;
	int rev = 0;
	deque<char> deq(all(s));
	rep(_,q) {
		int t;
		cin >> t;
		if (t == 1) {
			rev ^= 1;
		}
		else {
			int f;
			char c;
			cin >> f >> c;
			if (f == 1) {
				if (rev == 0)deq.push_front(c);
				else deq.push_back(c);
			}
			else {
				if (rev == 0)deq.push_back(c);
				else deq.push_front(c);
			}
		}
	}

	if (rev)reverse(all(deq));

	for (char c : deq)cout << c;
	cout << endl;



	return 0;
}

Measured memory_bytes: 976
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1e9+7;

int dp[100005][2];//dp[i][1] -> s未満、dp[i][0] ->sと等しい

int main(){
  string s;
  cin >> s;
  dp[0][0] = 1;
  int n = s.size();
  rep(i,s.size()) {
    // a+b = 0
    if (s[i] == '0') {
      dp[i+1][0] = dp[i][0];
      dp[i+1][1] = dp[i][1];
    } else {
      dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod;
    }
    //a+b = 1
    //a+b = 0の場合に足す
    if (s[i] == '0') {
      (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;//(1,0) or (0,1)の場合があるため2倍
    } else {
      (dp[i+1][0] += dp[i][0]*2 % mod) %= mod;
      (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;
    }
  }

  int res = (dp[n][0] + dp[n][1]) % mod;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1280
import java.io.*;
import java.util.StringTokenizer;
public class Main{
     
  
  public static int rec(int n,int k){    
    int r = 0;
    for(int i = 1 ; i < (1 << 10);i++){
      int c = Integer.bitCount(i);
      int sum = 0;
      if(c == n){
        for(int j = 0; j < 10; j++)
            if((i & (1 << j)) != 0)
              sum += j;
        if(sum == k)
          r++;     
      }  
    }    
    return r;  
  } 
  
  public static void main(String [] args)throws IOException{
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    
    while(true){
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      if( n == 0 && k == 0) 
        break;
      System.out.println(rec(n,k));   
    }  
  }


}

Measured memory_bytes: 9548
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())
dp = [n+1] * (n+1)
dp[n] = 0
for rest in xrange(n, 0, -1):
    for i in xrange(m):
        if c[i] <= rest:
            dp[rest - c[i]] = min(dp[rest - c[i]], 1 + dp[rest])
print dp[0]

Measured memory_bytes: 7540
N = int(input())
SP = [list(input().split()) for i in range(N)]
S = [SP[i][0] for i in range(N)]
P = [int(SP[i][1]) for i in range(N)]
ISP = []
for i in range(N):
    ISP.append([i+1,S[i],P[i]])
ISP.sort(key = lambda x:x[2],reverse = True)
ISP.sort(key = lambda x:x[1])
for i in range(N):
    print(ISP[i][0])

Measured memory_bytes: 3064
def exp(a):
    return (a + 1) / 2

n, k = map(int, input().split())
p = list(map(int, input().split()))

tmp = [0] * (n + 1) 
ans = 0

for i in range(1, n+1):
    if i <= k:
        tmp[i] = tmp[i-1] + exp(p[i-1])
    else:
        tmp[i] = tmp[i-1] - exp(p[i-k-1]) + exp(p[i-1])

print(max(tmp))


Measured memory_bytes: 71792
#line 1 "../lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>

using namespace std;

#line 2 "tmp.cpp"

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

  int n;
  cin >> n;
  vi a;
  REP(i, n) {
    int r, c;
    cin >> r >> c;
    if (i == 0)
      a.push_back(r);
    a.push_back(c);
  }

  vector<vi> dp(n + 1, vi(n + 1, 1e9));
  REP(k, n + 1) {
    REP(i, n + 1 - k) {
      if (k < 2) {
        dp[i][i + k] = 0;
      } else {
        REP(j, k) { dp[i][i + k] = min(dp[i][i + k], dp[i][i + j] + dp[i + j][i + k] + a[i] * a[i + j] * a[i + k]); }
      }
    }
  }

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

  return 0;
}



Measured memory_bytes: 3228
#include<bits/stdc++.h>
#include<math.h>
#include<vector>
using namespace std;
#define MAX 10009
#define MOD 1000000007
#define EPS 0.0000000001

int main()
{
    int A,B,K;
    scanf("%d %d %d",&K,&A,&B);
    if((A/K)!=(B/K)||A%K==0||B%K==0)
    {
        printf("OK");
    }
    else
    {
        printf("NG");
    }
    return 0;
}


Measured memory_bytes: 3824
n = int(input())
L = [None]+list(input().split())
even = []
odd = []
if n % 2 == 0:
    for i in range(1,1+n):
        if i % 2 == 0:
            even.append(L[i])
        else:
            odd.append(L[i])
    for x in even[::-1]:
        print(x,end=' ')
    for y in odd:
        print(y,end=' ')
    print()
else:
    for i in range(1,1+n):
        if i % 2 == 0:
            even.append(L[i])
        else:
            odd.append(L[i])
    for y in odd[::-1]:
        print(y,end=' ')
    for x in even:
        print(x,end=' ')
    print()

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

int main() {
  int Ans = 1e9;  // 回答：

  int K; cin >> K; // 円周
  int N; cin >> N; // 家の戸数
  vector<int> A(N); // 家の位置
  rep(i,N){cin >> A.at(i);}

  int wk_d=0; // 前向きに図った距離
  rep(i,N){
    if(i==0){   // 北端を経由しないパターン
      wk_d = A.at(N-1) - A.at(0);
    } else {    // 北端をまたがるパターン
      wk_d = K - A.at(i) + A.at(i-1);
    }
    Ans = min(Ans,wk_d);
  }
  
  cout << Ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
signed main(){
    int a,b;cin>>a>>b;
    if(a>=13){
        cout<<b;
    }else if( a<=5){
        cout<<0;
    }else cout<<b/2;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
#define ll long long

vector<pair<int,int> > adj[N];
int color[N];

void bipartite(int s){
    queue<int> q;
    q.push(s);
    color[s]=1;

    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].first;
            if(color[v]==0){
                if(adj[u][i].second%2==0){
                    color[v]=color[u];
                }
                else
                    color[v]=3-color[u];
                q.push(v);
            }
        }
    }

}

int main(){
    int T,i,j,n;

    cin>>n;
    memset(color,0,sizeof(color));
    for(i=1;i<=n-1;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);

        adj[u].push_back(make_pair(v,w));
        adj[v].push_back(make_pair(u,w));

    }
    bipartite(1);

    for(i=1;i<=n;i++){
        printf("%d\n",color[i]-1);
    }



return 0;
}


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

int main(){
    bitset<64> bs;
    int q;
    cin >> q;

    int op, i;
    while(q-- > 0){
        cin >> op;
        if(op == 0) scanf("%d", &i), cout << bs[i] << endl;
        if(op == 1) scanf("%d", &i), bs[i] = true;
        if(op == 2) scanf("%d", &i), bs[i] = false;
        if(op == 3) scanf("%d", &i), bs[i] = !bs[i];
        if(op == 4) printf("%d\n", bs.all());
        if(op == 5) printf("%d\n", bs.any());
        if(op == 6) printf("%d\n", bs.none());
        if(op == 7) printf("%d\n", bs.count());
        if(op == 8) printf("%llu\n", bs.to_ullong());
    }

    return 0;
}


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

// #define DEBUG

typedef pair <int, int> EDGE;
typedef map <EDGE, int> EDGES;
typedef map <string, int> HASH;

const int INF = 1 << 28;

EDGES G;
HASH H;

// return edge data
EDGE get_edge( int a, int b ) { return make_pair( a, b ); }
EDGE get_edge( string a, string b ) { return make_pair( H[a], H[b] );}

// for input
void input( string& a, string& b, int& x )
{
	int g1, g3;
	char g2, g4;
	cin >> g1 >> a >> g2 >> g3 >> g4 >> x >> b;
	cin.clear();
	cin.ignore();
}

int main( void )
{
	string a, b;
	int x, n;
#ifdef DEBUG
	int loop_cnt = 0;
#endif

	while ( cin >> n && n )
	{
#ifdef DEBUG
		loop_cnt++;
		cout << loop_cnt << "ñÚÌÀs" << endl;
#endif
		// initialize
		G = EDGES();
		H = HASH();

		int number = 0;
		for ( int i = 0; i < n; i++ )
		{
			input( a, b, x );
			// cout << "a = " << a << ", b = " << b << " is " << x << endl;

			if ( H.find( a ) == H.end() )
			{
				H[a] = number;
				number++;
			}
			if ( H.find( b ) == H.end() )
			{
				H[b] = number;
				number++;
			}

			// initialize
			G[get_edge(a,b)] = x;
			G[get_edge(b,a)] = -x;
		}

		// initialize
		for ( int i = 0; i < number; i++ )
		{
			for ( int j = 0; j < number; j++ )
			{
				if ( G.find( get_edge(i,j) ) == G.end() ) G[get_edge(i,j)] = INF;
			}
		}

		EDGES P = G;
		// Warshall-Floyd Algorithm
		for ( int k = 0; k < number; k++ )
		{
			for ( int i = 0; i < number; i++ )
			{
				for ( int j = 0; j < number; j++ )
				{
					if ( i == k || j == k ) continue;
					if ( P[get_edge(i,k)] == INF || P[get_edge(k,j)] == INF ) continue;
					if ( P[get_edge(i,j)] == INF )
					{
						P[get_edge(i,j)] = P[get_edge(i,k)] + P[get_edge(k,j)];
					}
					else
					{
						P[get_edge(i,j)] = min( P[get_edge(i,j)], P[get_edge(i,k)] + P[get_edge(k,j)] );
					}
				}
			}
		}
		// end of WF Algorithm

		// for debug
#ifdef DEBUG
		cout << "³ÌOt" << endl;
		for ( int i = 0; i < number; i++ )
		{
			for ( int j = 0; j < number; j++ )
			{
				if ( G[get_edge(i,j)] == INF ) cout << "x ";
				else cout << G[get_edge(i,j)] << " ";
			}
			cout << endl;
		}
		cout << endl;
#endif
		// for debug
#ifdef DEBUG
		cout << "ASYKpã" << endl;
		for ( int i = 0; i < number; i++ )
		{
			for ( int j = 0; j < number; j++ )
			{
				if ( P[get_edge(i,j)] == INF ) cout << "x ";
				else cout << P[get_edge(i,j)] << " ";
			}
			cout << endl;
		}
		cout << endl;
#endif

		// check
		bool is_correct = true;
		for ( int i = 0; is_correct && i < number; i++ )
		{
			for ( int j = 0; is_correct && j < number; j++ )
			{
				if ( G[get_edge(i,j)] == INF ) continue;
				if ( G[get_edge(i,j)] != P[get_edge(i,j)] ) is_correct = false;
			}
		}

		cout << ( is_correct ? "Yes" : "No" ) << endl;
	}

	return 0;
}

Measured memory_bytes: 3452
N = int(input())
C = [0]*(N-1)
S = [0]*(N-1)
F = [0]*(N-1)
for i in range(N-1):
    C[i],S[i],F[i] = map(int,input().split())

total_time = 0
for i in range(N-1):
    total_time = S[i]+C[i]
    for j in range(i+1,N-1):
        if total_time < S[j]:
            total_time = S[j]
        elif total_time % F[j] != 0:
            total_time += F[j] - (total_time%F[j])
        total_time += C[j]
    print(total_time)
print(0)


Measured memory_bytes: 41836
import java.util.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        if(Math.abs(N - M)>1){
            System.out.println(0);
            return;
        }
        long nf = 1L;
        long mf = 1L;
        for(int i=N; i>=2; i--){
            nf = nf * i;
            nf = nf % 1000000007;
        }
        for(int i=M; i>=2; i--){
            mf = mf * i;
            mf = mf % 1000000007;
        }
        if(N==M){
            System.out.println((nf * mf * 2) % 1000000007);
        }
        else{
            System.out.println((nf * mf) % 1000000007);
        }
    }
}

Measured memory_bytes: 21844