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

using namespace std;

#define REPEAT(i, N) for (int i = 0; i < (N); i++)

int main() {
  int W, H, x, y;
  
  cin >> W >> H >> x >> y;
  
  cout << setprecision(9) << (double)W * H / 2.0 << " ";
  
  if (2 * x == W && 2 * y == H) {
    cout << 1;
  } else {
    cout << 0;
  }
  
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    using namespace std;
    #define INF 10000000;
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
    #define vec(n) vector<int>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

  
  
    int main(){
      int n;
      cin >> n;
      long power = 1;
      REP(i,1,n+1){
        power *= i;
        if(power > 1000000007)power %= 1000000007;
      }
      
      cout << power <<endl;
    }

    


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

using namespace std;

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

    vector<long long> backet(100001, 0);
    int a, b, i;
    for (i=1; i<=100000; i++) backet[i] = 0;
    for (i=0; i<N; i++) {
        cin >> a >> b;
        backet[a] += b;
    }
    for (int i=1; i<=100000; i++) {
        if (K <= backet[i]) {
            cout << i << endl;
            break;
        }
        K -= backet[i];
    }
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int m,f,r;
    while(1){
        cin>>m>>f>>r;
        if (m==-1&&f==-1&&r==-1) break;
        else if (m==-1||f==-1) cout<<"F"<<endl;
        else if (m+f>=80) cout<<"A"<<endl;
        else if (m+f>=65) cout<<"B"<<endl;
        else if (m+f>=50) cout<<"C"<<endl;
        else if (m+f>=30){
            if (r>=50) cout<<"C"<<endl;
            else cout<<"D"<<endl;
        }
        else cout<<"F"<<endl;
    }
}


Measured memory_bytes: 3084
N, M, Q = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(Q)]

max_score = 0


def dfs(start, end, depth, numbers):
    if depth == N:
        global max_score
        for n in range(start, end + 1):
            A = (*numbers, n)
            score = 0
            for a, b, c, d in records:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            max_score = max(max_score, score)
    else:
        for n in range(start, end + 1):
            dfs(start=n, end=end, depth=depth + 1, numbers=(*numbers, n))


dfs(start=1, end=M, depth=1, numbers=())
print(max_score)


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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int func(int A, int B, int C){

	if(A % 2 == 1 or B % 2 == 1 or C % 2 == 1) return 0;
	if(A == B and B == C) return -1;

	return func((B+C)/2, (C+A)/2, (A+B)/2) + 1;

}



int main(void){

	int A, B, C; cin >> A >> B >> C;
	int ans = func(A, B, C);

	cout << ans << endl;


	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);

    	while(true){
        	int H = scan.nextInt();
        	int W = scan.nextInt();

        	if(H == 0 && W == 0) break;

        	for(int i = 0; i < H; i++){
        		for(int j = 0; j < W; j++){
        			if(i == 0 || i == H - 1 ){
        			    System.out.print("#");
        			}else if(j == 0 || j == W - 1){
        				System.out.print("#");
        			}else{
        				System.out.print(".");
        			}
        		}
        		System.out.println();
        	}
        	System.out.println();
    	}
    }
}

Measured memory_bytes: 32420
#include"stdio.h"
#include"stdlib.h"
struct num
{
  int n;
  struct num *next;
};
int main()
{
  int n;
  int q;
  struct num *S;
  int *T;
  struct num *p;
  int i;
  int m;
  int C=0;
  S=(struct num*)malloc(sizeof(struct num));
  S->next=NULL;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&m);
      for(p=S;p->next!=NULL;p=p->next)
        {
          if(p->next->n==m)break;
        }
      if(p->next==NULL)
        {
          p->next=(struct num*)malloc(sizeof(struct num));
          p->next->n=m;
          p->next->next=NULL;
        }
    }
  scanf("%d",&q);
  T=(int*)malloc(sizeof(int)*q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&T[i]);
    }
  for(p=S->next;p!=NULL;p=p->next)
    {
      for(i=0;i<q;i++)
        {
          if(p->n==T[i])
            {
              C++;
              break;
            }
        }
    }
  printf("%d\n",C);
}


Measured memory_bytes: 2068
ll, rr = map(int, input().split())
if rr - ll >= 2019:
    print(0)
    exit()

l = ll % 2019
r = rr % 2019

if l > r:
    print(0)
    exit()

ans = 10**9
for i in range(l, r + 1):
    for j in range(i+1, r+1):
        x = (i * j) % 2019
        ans = min(x, ans)

print(ans)


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#define N 20
int
main (void)
{
  char str[N + 1];
  char out[N + 1];
  char buf, len;
  scanf ("%s", str);
  len = strlen (str);
  for (buf = len; buf >= 0; buf--)
    out[len - buf] = str[buf - 1];
  out[len] = '\0';
  printf ("%s\n", out);
  return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
int A[3][3];

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> s(m);
  vector<char> c(m);
  for (int i = 0; i < m; ++i) cin >> s[i] >> c[i];
  for (int i = 0; i < m; ++i) {
    for (int j = i+1; j < m; ++j) {
      if (s[i] == s[j] && c[i] != c[j]) {
        cout << "-1\n";
        return 0;
      }
    }
  }
  string ans(n, '0');
  if (n != 1) ans[0] = '1';
  for (int i = 0; i < m; ++i) ans[s[i] - 1] = c[i];
  if (n != 1 && ans[0] == '0') {
    cout << "-1\n";
    return 0;
  }
  cout << ans << endl;
}

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

int main(void){
        int n,i;
        cin >> n;
        vector<int> a(n);
        for (i=0;i<n;i++){
                cin >> a[i];
        }
        sort(a.begin(),a.end(),greater<int>());

//      for(i=0;i<n;i++){
//              cout << a[i] << endl;
//      }

        int sum_alice=0,sum_bob=0;
        for(i=0;i<n;i++)
        {
                if(i%2==0){
                        sum_alice+=a[i];
                }else{
                        sum_bob+=a[i];
                }
        }
//      cout << "alice=" << sum_alice << "\n" << "bob=" << sum_bob << endl;
        int ans = sum_alice - sum_bob;
        cout << ans << endl;
//      cout << "alice-bob=" << sum_alice - sum_bob << endl ;

        return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s, t, u;
	int a, b;
	cin >> s >> t >> a >> b >> u;
	if(u == s) a--;
	else b--;
	cout << a << " " << b << endl;
}

Measured memory_bytes: 256
N = int(input())
data = [0 for _ in range(9)]
a = list(map(int, input().split()))
for i in range(N):
    x = a[i]
    if 0 <= x <= 399:
        data[0] = 1
    elif 400 <= x <= 799:
        data[1] = 1
    elif 800 <= x <= 1199:
        data[2] = 1
    elif 1200 <= x <= 1599:
        data[3] = 1
    elif 1600 <= x <= 1999:
        data[4] = 1
    elif 2000 <= x <= 2399:
        data[5] = 1
    elif 2400 <= x <= 2799:
        data[6] = 1
    elif 2800 <= x <= 3199:
        data[7] = 1
    else:
        data[8] += 1

Sum = 0
for i in range(8):
    if data[i] != 0:
        Sum += 1
m = max(1, Sum)
M = Sum + data[8]

print(m,M)



Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 510000;
const int INF = 1e9;
const double pi=acos(-1);

int main(){
  int n;
  cin >> n;
  vector<ll>a(n),b(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  
  vector<ll>gap;
  ll sum = 0;
  int num = 0;
  
  rep(i,n){
    ll diff = b[i] - a[i];
    if(diff>0){
      num++;
      sum += diff;
    }
    else gap.push_back(-diff);
  }
  
  if(num==0){
    cout << 0 << endl;
    return 0;
  }
  sort(gap.begin(),gap.end(),greater<ll>());
  
  ll plus=0;
  int res = num;
  rep(i,gap.size()){
    plus+=gap[i];
    res++;
    if(plus>=sum){
      break;
    }
  }
  if(plus>=sum) cout << res << endl;
  else cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 2936
#include <stdio.h>
int main(void){
    int i, c = 1, n, a[200000], result = 0;
    
    scanf("%d", &n);
    
    for( i = 0; i < n; i++ ){
        scanf("%d", &a[i]); 
    }
    
    for( i = 0; i < n; i++ ){
        if( a[i] != c ){
            result++;
        } else {
            c++;
        }
    }
    
    if( c == 1 ){
        printf("-1\n");
    } else {
        printf("%d\n", result);
    }
    
    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    int N;
    cin >> N;
    double total = 0;
    string val, unit;
    for (int i = 0; i < N; i++) {
        cin >> val >> unit;
        if (unit == "BTC") {
            total += ::atof(val.c_str()) * 380000.0;
        } else {
            total += ::atof(val.c_str());
        }
    }
    cout << total << endl;
}



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

typedef long long ll;
int n, k, a[200000];
string s;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> s;
    for (int i = 0; i < s.size(); ++i)
        s[i] = (((((s[i] - 'A') + n) % 26) + 26) % 26) + 'A';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
n=gets.to_i
arr=n.times.map{gets.to_i}
as=Hash.new(0)
cnt=0
for i in 0..n-1
if as[arr[i]].even?
cnt+=1
as[arr[i]]+=1
else
cnt-=1
as[arr[i]]+=1
end
end
puts cnt


Measured memory_bytes: 9084
counter = 0

repeater = int(input())
lst = []
for i in range(repeater):
     lst.append(''.join(sorted(input())))

import collections
dic = collections.Counter(lst)

for i in dic.values():
    if i == 0:
        continue
    counter = counter +  i * (i - 1) / 2
print(int(counter))

Measured memory_bytes: 19788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;


class Main{
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		int H=sc.nextInt();
		int W=sc.nextInt();
		pl(Math.max((N+1-W)*(N+1-H),0));

	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, q;
pair<int, int> p[3002];
int dp[3002];
int fact[200002];

int MUL(int x, int y) {
	return (ll)x * (ll)y % MOD;
}

int pot(int x, int y) {
	if (y == 1) return x;
	ll tren = pot(x, y/2);
	tren *= tren;
	tren %= MOD;
	if (y % 2 == 1) {
		tren *= x;
		tren %= MOD;
	}
	
	return tren;
}

int povrh(int x, int y) {
	y = MUL(fact[y], fact[x-y]);
	x = fact[x];
	
	y = pot(y, MOD-2);
	x = MUL(x, y);
	return x;
}

int main () {

	cin >> n >> m >> q;
	for (int i = 0; i < q; i++) cin >> p[i].X >> p[i].Y;
	fact[0] = 1;
	for (int i = 1; i <= n+m; i++) {
		fact[i] = MUL(fact[i-1], i);
	}
	sort(p, p + q);

	int sol = povrh(n+m-2, n-1);
	int ne = 0;
	for (int i = 0; i < q; i++) {
		dp[i] = povrh(p[i].X+p[i].Y-2, p[i].X-1);
		
		for (int j = 0; j < i; j++) {
			if (p[j].Y <= p[i].Y) {
				dp[i] -= MUL(dp[j], povrh(p[i].X-p[j].X+p[i].Y-p[j].Y, p[i].X-p[j].X));
				
				if (dp[i] < 0) dp[i] += MOD;
			}
		}
		
		ne += MUL(dp[i], povrh(n-p[i].X+m-p[i].Y, n-p[i].X));
		ne %= MOD;
	}
	
	sol = (sol - ne + MOD) % MOD;
	cout << sol;

	return 0;
}


Measured memory_bytes: 4424
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M, C;
	cin >> N >> M >> C;
  	int B[M];
  	for(int i=0;i<M;i++) cin >> B[i];
  	int A[N][M];
    int Count=0;
    for(int i=0;i<N;i++)
    {
      int total=0;
      for(int j=0;j<M;j++)
      {
        cin >> A[i][j];
        total+=A[i][j]*B[j];
      }
      if(total + C > 0) Count++;
    }
    cout<< Count <<endl;
    
  	return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
rep = sorted([tuple(map(int, input().split())) for i in range(m)], key= lambda x: -x[1])
i = 0
for b, c in rep:
    while i < n and b:
        if a[i] < c:
            a[i] = c
            i += 1
            b -= 1
        else:
            break
print(sum(a))

Measured memory_bytes: 32200
n = int(input())
s = input()

r = [0] * n
g = [0] * n
b = [0] * n
ri = gi = bi = 0
for i, c in enumerate(s):
  if c == "R":
    ri += 1
  elif c == "G":
    gi += 1
  if c == "B":
    bi += 1
  r[i] = ri
  g[i] = gi
  b[i] = bi

 
ans = r[-1] * g[-1] * b[-1]

for k in range(2, n):
  for j in range(1, k):
    if s[k] == s[j]:
      continue
    i = 2 * j - k
    if i < 0 :
      continue
    if s[k] != s[i] and s[j] != s[i]:
      ans -= 1

print(ans)

Measured memory_bytes: 9308
X,K,D=map(int, input().split())
d=abs(X)//D
if d>=K:
	if X<0:ans=X+K*D
	else:ans=X-K*D

else:
	if X<0:
		temp=X+d*D
		if (K-d)%2==0:
			ans=temp
		else:
			ans=temp+D
	else:
		temp=X-d*D
		if (K-d)%2==0:
			ans=temp
		else:
			ans=temp-D

print(abs(ans))

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

int main() {
	string s; cin >> s;

	for (char c = 'a'; c <= 'z'; c++) {
		bool ok = false;
		for (int i = 0; i < s.size(); i++) {
			if (c == s[i])ok = true;
		}
		if (!ok) {
			cout << c << endl;
			return 0;
		}
	}
	cout << "None" << endl;

	return 0;
}

Measured memory_bytes: 3740
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			String input = br.readLine();
			String[] splitInput = input.split(" ");

			int a = Integer.parseInt(splitInput[0]);
			int b = Integer.parseInt(splitInput[1]);
			int c = Integer.parseInt(splitInput[2]);
			
			if (
					!(
					       (a >= 0 && a <= 100)
					    && (b >= 0 && b <= 100)
					    && (c >= 0 && c <= 100)
				     )
				) {
				throw new IllegalArgumentException();
			}
			
			String ans;
			if ((a < b) && (b < c)) {
				ans = "Yes";
			} else {
				ans = "No";
			}
			
			System.out.println(ans);
		
		} catch(NumberFormatException e) {
			e.printStackTrace();
		} catch(IllegalArgumentException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 24180
def main(n):

    if (n <= 26):
        ans.append(chr(96 + n))
        ans.reverse()
        print(''.join(ans))
    elif( n % 26 == 0):
        ans.append(chr(122))
        main(n//26 - 1)
    else:
        ans.append(chr(96 + n%26))
        main(n//26)
        

n = int(input())
ans = []

main(n)




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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int  INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll mod = 998244353;


const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
ll pow_mod(ll n, ll k, ll m) {
	ll r = 1;
	for (; k > 0; k >>= 1) {
		if (k & 1)r = (r*n) % m;
		n = (n*n) % m;
	}
	return r;
}//nのk乗をmで割った時のあまり



int main() {

	ll n, m, k;
	cin >> n >> m >> k;
	if (m == 1 && k != n - 1) {
		cout << 0 << endl;
		return 0;
	}
	if (m == 1) {
		cout << m << endl;
		return 0;
	}

	COMinit();

	ll ans = 0;

	while (k != -1) {
		ll a = COM(n - 1, k);
		a *= m;

		a %= mod;
		ll b = pow_mod(m - 1, n - k - 1, mod);

		b %= mod;

		ans += a * b%mod;
		ans %= mod;


		k--;
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 15592
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, Q, l1, r1, l2, r2;
string S;
char T[200000], D[200000];

int main(){
	cin >> N >> Q >> S;
	for (int i = 0; i < Q; ++i) {
		cin >> T[i] >> D[i];
	}
	l1 = -1;
	r1 = N;
	while (l1 + 1 != r1) {
		int m = (l1 + r1) / 2;
		int p = m;
		bool f = true;
		for (int i = 0; i < Q; ++i) {
			if (T[i] == S[p]) {
				if (D[i] == 'L') {
					--p;
					if (p == -1) {
						f = false;
						break;
					}
				}
				else {
					++p;
					if (p == N) {
						break;
					}
				}
			}
		}
		if (f) {
			r1 = m;
		}
		else {
			l1 = m;
		}
	}
	l2 = -1;
	r2 = N;
	while (l2 + 1 != r2) {
		int m = (l2 + r2) / 2;
		int p = m;
		bool f = true;
		for (int i = 0; i < Q; ++i) {
			if (T[i] == S[p]) {
				if (D[i] == 'L') {
					--p;
					if (p == -1) {
						break;
					}
				}
				else {
					++p;
					if (p == N) {
						f = false;
						break;
					}
				}
			}
		}
		if (f) {
			l2 = m;
		}
		else {
			r2 = m;
		}
	}
	cout << r2 - r1 << endl;
	return 0;
}

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

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

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

const LL mod = 1000000007;

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

    LL ans = 0;
    REP(i, X+1) {
        LL s = i * (i+1) / 2;
        if (s >= X) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pii;
int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> A(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }
  ll sum = 0;
  ll res = 0;
  for (int i = 0; i <= N; i++) {
    sum += A[i];
    A[i] = (sum - i) % K;
  }
  cout << endl;
  unordered_map<int, deque<int>> memo;
  for (int i = 0; i <= N; i++) {
    while (!memo[A[i]].empty() && (i - memo[A[i]].front() >= K)) {
      memo[A[i]].pop_front();
    }
    res += memo[A[i]].size();
    memo[A[i]].push_back(i);
  }
  cout << res << endl;
  return 0;
}


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

int main() {
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int cnt = 0;

    for(int i = 0 ; i <= a ; i++){
        for(int j = 0 ; j <= b ; j++){
            for(int k = 0 ; k <= c ; k++){
                if(i * 500 + j * 100 + k * 50 == x){
                    cnt++;
                }
            }
        }
    }

    cout << cnt << endl;
    

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;


int main() {
  int n, k; cin >> n >> k;
  vector<int> p(n);
  rep(i, n) cin >> p[i];

  sort(all(p));
  ll sum = 0;
  rep(i, k) sum += p[i];
  cout << sum << endl;
}


Measured memory_bytes: 3632
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let a = read_vec::<i64>();
    let mut b = read_vec::<i64>();

    let mut heap = BinaryHeap::new();
    for i in 0..n {
        heap.push((b[i], i));
    }

    let mut ans = 0;
    while let Some((bnum, i)) = heap.pop() {
        if bnum == a[i] {
            continue;
        }
        if bnum < a[i] {
            println!("-1");
            return;
        }
        let mut left = i + n - 1;
        if left >= n {
            left -= n;
        }
        let mut right = i + 1;
        if right == n {
            right = 0;
        }

        if (b[i] - a[i]) % (b[left] + b[right]) == 0 {
            let coef = (b[i] - a[i]) / (b[left] + b[right]);
            ans += coef;
            b[i] -= coef * (b[left] + b[right]);
            continue;
        }

        let coef = (b[i] - 1) / (b[left] + b[right]);
        if coef <= 0 {
            debug!(b[i], (b[left] + b[right]), a[i]);
            println!("-1");
            return;
        }
        b[i] -= coef * (b[left] + b[right]);
        heap.push((b[i], i));
        ans += coef;
    }
    println!("{}", ans);
}

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

int main() {
	int N;
	string S;
	long long p;
	int q;
	int r;
	long long aa;

	cin >> N;
 	vector<int> a0(5);
 	vector<int> a1(11);
 	vector<int> a2(N);
 	vector<int> a5(N);
	vector<vector<long long >> x(25, vector<long long >(25));

   	rep(i,N) {
   		rep(j,5) a0.at(j)=0;
   		rep(j,10) a1.at(j)=0;
		cin >> S;
		p=0;
		q=-1;
		aa=0;
		r=S.size();
   		rep(j,r) {
			if(S.at(j)=='.') q=0;
			else if(q<0) {
				a0.at(p)=S.at(j)-'0';
				p++;
			} else {
				a1.at(q)=S.at(j)-'0';
				q++;
			}
		}
		if (p>0) {
	   		rep(j,p) {
				aa*=10;
				aa+=a0.at(j);
			}
		}
   		rep(j,9) {
			aa*=10;
			aa+=a1.at(j);
		}
   		rep(j,20) {
	        a2.at(i)=j;
			if (aa%2>0) break;
			aa/=2;
		}
   		rep(j,20) {
	        a5.at(i)=j;
			if (aa%5>0) break;
			aa/=5;
		}
	}

   	rep(i,25) {
   		rep(j,25) {
			x.at(i).at(j)=0;
		}
	}
   	rep(i,N) {
			x.at(a2.at(i)).at(a5.at(i))++;
	}

	p=0;
   	rep(i1,21) {
	   	rep(i2,21) {
			if(i1+i2>=18){
	   			rep(j1,21) {
   					rep(j2,21) {
						if(j1+j2>=18) {
							p+=x.at(i1).at(j1)*x.at(i2).at(j2);
							if((i1==i2)&&(j1==j2)) p-=x.at(i1).at(j1);
						}
					}
				}
			}
		}
	}
	cout << p/2 << endl;
	return 0;
}

Measured memory_bytes: 4840
#include <iostream>
#include<cstring>
using namespace std;
int main(void){
    int x;
    // Here your code !
    cin>>x;
    int sum=0;
    int cnt=0;
    for(int i=1;sum<x;i++){
        cnt++;
        sum+=i;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc113/tasks/abc113_b

N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))


ans = 0
min_d = 50000
for i in range(N):
    t = T - H[i] * 0.006
    d = abs(A - t)
    if d < min_d:
        min_d = d
        ans = i + 1

print(ans)


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
#define N 3010
long long dp[N][N];
int main ()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> dp[i][i];
        for (int j = i - 1; j > 0; j --) {
            dp[i][j] = max(dp[i][i] - dp[i - 1][j], dp[j][j] - dp[i][j + 1]);
        }
    }
    cout << dp[n][1];
    return 0;
}

Measured memory_bytes: 69120
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll inf=1e18;
int N;
ll L[5000],R[5000];
ll dp[2][2501][2501];
int main(){
	cin>>N;
	rep(i,N) cin>>L[i]>>R[i];
	rep(i,N-1) rep(j,N-1) if(L[j]+R[j]<L[j+1]+R[j+1]) swap(L[j],L[j+1]),swap(R[j],R[j+1]);
	rep(i,2) rep(j,2501) rep(k,2501) dp[i][j][k]=inf;
	dp[0][0][0]=0;
	rep(n,N){
		rep(c,2) rep(l,n+1-c){
			int r=n-l-c;
			if(l>2500||r>2500) continue;
			if(dp[c][l][r]==inf) continue;
			if(c==0) chmin(dp[1][l][r],dp[0][l][r]+N/2*(L[n]+R[n]));
			if(l<2500) chmin(dp[c][l+1][r],dp[c][l][r]+l*(L[n]+R[n])+R[n]);
			if(r<2500) chmin(dp[c][l][r+1],dp[c][l][r]+r*(L[n]+R[n])+L[n]);
		}
	}
	ll ans=inf;
	rep(c,2) rep(l,N+1-c){
		int r=N-l-c;
		if(l<=2500&&r<=2500) chmin(ans,dp[c][l][r]);
	}
	cout<<ans<<endl;
}


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

int main(){
    
    int num1,num2;
    
    char ch[1000][2],ch2[100000];
    
    while(true){
    
    std::cin>>num1;
    
        if(num1==0)
            break;
        
    for(int i=0;i<num1;i++)
        std::cin>>ch[i][0]>>ch[i][1];
    
    std::cin>>num2;
    
    std::string str(num2,'a');
    
    for(int i=0;i<num2;i++){
        std::cin>>ch2[i];
        str[i]=ch2[i];
        for(int j=0;j<num1;j++){
            if(str[i]==ch[j][0]){
                str[i]=ch[j][1];
                goto flag1;
            }
        }
    flag1:;
    }
    
    std::cout<<str<<std::endl;
        
    }
    
    return 0;
}

Measured memory_bytes: 3272
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int N;
	cin >> N;
	VI A(N*2);
	REP(i, 2*N) {
		cin >> A[i];
	}
	SORT(A);
	int ans = 0;
	for (int i = 0; i < 2*N; i += 2) {
		ans += A[i];
		//cout << A[i];
	}

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



Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[12];
int k;
bool f=0;
int main()
{
	scanf("%s",s);
	int n=strlen(s);
	if(s[0]!='A')f=1;
	for(int i=1;i<n;i++)
		if(s[i]=='C'&&i>1&&i<n-1)k++;
		else	if(!(s[i]>='a'&&s[i]<='z'))
					f=1;
	if(k!=1)f=1;
	if(f)
		printf("WA");
	else printf("AC");
	//return 0;
}

Measured memory_bytes: 128
/*
* @author:  codancer
* @createTime:  2020-02-17, 09:39:06
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef pair<int,int> pii;
ll n,k,ans,l,r;
ll a[200010];
bool check(ll x){
	ll cnt=0;// the number that less than x
	for(int i=1;i<=n;i++){
		ll num=0;
		if(a[i]==0){
			if(x>0) cnt+=n-1;
		}else{
			if(a[i]>0){
				ll h=x/a[i];
				if(x%a[i]&&(x>0)){
					++h;
				}
				num=lower_bound(a+1,a+n+1,h)-a-1;
			}
			else{
				ll h=x/a[i];
				if(x%a[i]&&(x>0)){
					h--;
				}
				ll great=upper_bound(a+1,a+n+1,h)-a-1;
				num=n-great;
			}
			cnt+=num;
			if(a[i]*a[i]<x) --cnt;
		}
	}
	cnt/=2;
	return cnt<k;
}
// bool chk(ll x)
// {
// 	ll cnt=0,t1,t2;
// 	for(int i=1;i<=n;++i)
// 		if(a[i])
// 		{
// 			t1=t2=x/a[i];
// 			if(x%a[i])
// 			{
// 				if((x<0 && a[i]>0) || (x>0 && a[i]<0)) --t1;
// 				else ++t2;
// 			}
// 			if(a[i]<0) cnt+=n+1-(upper_bound(a+1,a+n+1,t1)-a);
// 			if(a[i]>0) cnt+=lower_bound(a+1,a+n+1,t2)-a-1;
// 			if(a[i]*a[i]<x) --cnt;
// 		}else if(x>0) cnt+=n-1;cnt>>=1;return cnt<k;
// }

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	l=-1e18,r=1e18;
	ll ans;
	// cout<<check(-6)<<endl;
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)){
			 l=mid+1;
			 ans=mid;
		}
		else{
			r=mid-1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
S = input()
flg = True
while flg:
    if S == "":
        flg = False
        print("YES")
    elif S[-5:] == "dream":
        S = S[:-5]
    elif S[-7:] == "dreamer":
        S = S[:-7]
    elif S[-5:] == "erase":
        S = S[:-5]
    elif S[-6:] == "eraser":
        S = S[:-6]
    else:
        flg = False
        print("NO")

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

int main ()
{
	int h, m, s, t;
	cin >> t;
	h = t / 3600;
	t = t % 3600;
	m = t / 60;
	s = t % 60;
	cout << h << ":" << m << ":" << s << endl; 
	return 0;
} 


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, ce = 0, nw = 0, ne = 0, ans;
  string s;
  cin >> n >> s;
  ans = n;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'E') ce++;
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == 'E') {
      ne++;
      ans = min(ans, nw + ce - ne);
    }
    else if (s[i] == 'W') {
      ans = min(ans, nw + ce - ne);
      nw++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define show(x) cout << #x << " : " << x << endl;

bool cmp(pair < int, int > p1, pair < int, int > p2)
{
  return p1.second < p2.second;
}
int main ()
{
 int n, i, mx = -1;
 long long sum = 0, taken = 0;
 cin >> n;
 vector < pair < int, int > > v(n+1);
 for(i = 1; i <= n; i++)
 {
   cin >> v[i].first >> v[i].second;
   sum += v[i].first;
   mx = max(mx, v[i].second);
 }
 if(mx < sum)
 {
   cout << "No" << endl;
   exit(0);
 }
 sort(v.begin(), v.end(), cmp);
 bool pos = true;
 for(i = 1; i <= n; i++)
 {
   if(v[i].second < v[i].first + taken)
   {
     pos = false;
     break;
   }
   taken += v[i].first;
 }
 if(pos == true) cout << "Yes" << endl;
 else cout << "No" << endl;
}

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

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

    int ans = 1; // i=0は必ず条件を満たす
    int minimum = P.at(0);

    for(int i=1; i<N; ++i){
        if(P.at(i) == min(minimum, P.at(i))){
            ans++;
            minimum = P.at(i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
n = int(input())
l = []
ll = [0] * n

for _ in range(n):
    l.append(input())

l.sort()

i = 0

while i < n:
    cnt = 1

    while i + cnt < n and l[i] == l[i + cnt]:
        cnt += 1

    ll[i] = cnt
    i += cnt

m = max(ll)

for x in range(n):
    if ll[x] == m:
        print(l[x])

Measured memory_bytes: 20168
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ll long long
#define MOD 1000000007
#define MAX 100000010
using namespace std;

int main(){
  int h,n;
  cin >> h >> n;
  int a[n],b[n];
  REP(i,n) cin >> a[i] >> b[i];
  int ans = MAX;
  
  int dp[h+10010]; //dp[i] = 体力をi減らすために必要な魔力の最小値
  REP(i,h+10010) dp[i] = MAX;
  dp[0] = 0;
  
  REP(i,h+10){
    REP(j,n){
      dp[i+a[j]] = min(dp[i+a[j]], dp[i]+b[j]);
      if(i+a[j] >= h) ans = min(ans, dp[i+a[j]]);
    }
  }
  
  cout << ans;
  return 0;
}

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

int main(void) {
    string S;
    
    cin >> S;
    
    for (int i = 0; i < S.length(); i ++) {
        S[i] = 'x';
    }
    
    cout << S << endl;
    
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

a, b, c, d = map(int, input().split())
dp = [[0] * (d - b + 1) for _ in range(c - a + 1)]

dp[0][0] = 1
for i in range(c - a + 1):
    for j in range(d - b + 1):
        if i > 0:
            dp[i][j] += dp[i-1][j] * (b+j)
        if j > 0:
            dp[i][j] += dp[i][j-1] * (a+i)
        if i > 0 and j > 0:
            dp[i][j] -= dp[i-1][j-1] * (b+j-1) * (a+i-1)
        dp[i][j] %= 998244353

print(dp[-1][-1])

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

#define db(x) cout<<x<<'\n'
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define repi(i,n) for(int i=0;i<(n);++i)
//#define repA(i,a,n) for(int i=a;i<=(n);++i)
//#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define ll long long int
#define endl '\n'
#define lld long long double
#define vi vector<int> 
#define vl vector<ll> 
#define vb vector<bool> 
#define vvi vector<vector<int>  >
#define err(t) cout<<"Error : "<<t<<endl;
#define all(v) v.begin(),v.end()
#define mp make_pair
#define M 100000
#define MD 1000000007 //998244353
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= (b); i++)
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define vec(a) vector<a >
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll binpow(ll a,ll b){	if(a==0) return 0; if(b==0) return 1;ll ans=1;while(b>0){if(b&1) ans=ans*a; a=a*a; b=b>>1;}	return ans;}
template <typename T> 
T Min(T a,T b){ return a<b?a:b; }
template <typename T>
T Max(T a,T b){ return a>b?a:b; }

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	// int n;cin>>n;
	// string s;cin>>s;
	
	ll n;cin>>n; vl a(n); repi(i,n) cin>>a[i];
	sort(all(a));
	reverse(all(a));
	ll ans=0;
	priority_queue<ll> p;
	repi(i,n){
		if(p.empty()){
			p.push(a[i]);
		}
		else{
			ans+=p.top();
			p.pop();
			p.push(a[i]);
			p.push(a[i]);
		}
	}
	db(ans);
	
	/*
	int test1;cin>>test1;while(test1--){ 
			
	 }
	 //*/
return 0;
}



Measured memory_bytes: 6856
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


int main()
{
	int x;
	cin >> x;
	
	int a, b, s, t;
	bool flag = 0;
	//正、負
	for(int i=1; i<=100; i++){
		for(int j=1; j<=i; j++){
			s = i*i*i*i*i;
			t = j*j*j*j*j;
			if(s+t == x){
				a = i;
				b = j;
				flag = true;
				break;
			}
		}
		if(flag)break;
	}

	if(flag){
		cout << a << " " << (-1)*b << endl;
		return 0;
	}

	//正、正
	for(int i=1; i<=200; i++){
		for(int j=0; j<i; j++){
			s = i*i*i*i*i;
			t = j*j*j*j*j;
			if(s-t == x){
				a = i;
				b = j;
				flag = true;
				break;
			}
		}
		if(flag)break;
	}

	if(flag){
		cout << a << " " << b << endl;
		return 0;
	}
}


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

int main() {
	// your code goes here
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	a+=b;
	c+=d;
	if(a>c)
	cout<<"Left";
	else if(a==c)
	cout<<"Balanced";
	else cout<<"Right"<<endl;
	return 0;
}

Measured memory_bytes: 256
import math

n, d = map(int, input().split())
fealds = [list(map(int, input().split())) for _ in range(n)]
count = 0
for i in range(n):
    distance = math.sqrt(fealds[i][0] ** 2 + fealds[i][1] ** 2)
    if distance <= d:
        count += 1
print(count)


Measured memory_bytes: 45284
#include<stdio.h>

#define Max 200000

int main(){
  int i, j, n, R[Max], minv, maxv;

  scanf("%d", &n);

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

  maxv = R[1] - R[0];
  minv = R[0];

  for(j = 1 ; j <= n - 1 ; j++){
    //if(minv > R[j]) minv = R[j];
    if(maxv < R[j] - minv) maxv = R[j] - minv;
    if(minv > R[j]) minv = R[j];
  }

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

  return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define cinv(n,vec) VL (vec)(n);for(auto&v:vec)cin>>v;
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t make_tuple
#define eb emplace_back
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a),greater<>())
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define debgp(a) cout<<#a<<" "<<a.fi<<" : "<<a.se<<endl
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define out(a) cout<<(a)<<endl
#define cont const auto
#define fi first
#define se second
#define V vector
#define P pair
#define T tuple
#define VV(type,name,y,x,a) vector<vector<type>> name = vector<vector<type>>(y,vector<type>(x,a))
#define PQ priority_queue
typedef long long ll;
typedef double D;
typedef long double LD;
typedef string str;
typedef vector<ll> VL;
typedef pair<ll,ll> PL;
typedef vector<pair<ll,ll>> VP;
typedef tuple<ll,ll,ll> T3;
typedef tuple<ll,ll,ll,ll> T4;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int H,W;
  cin>>H>>W;
  V<str> S(H);
  rep(i,H)cin>>S[i];

  bool can=false;
  queue<T3> que; // Ypos,Xpos,turn
  VV(bool,visited,H,W,false);
  VV(ll,score,H,W,1e12);
  int dx4[]={1,0,-1,0},dy4[]={0,1,0,-1};
  que.push(m_t(0,0,1));
  visited[0][0]=true;
  
  while(!que.empty()){
    ll y,x,p;
    tie(y,x,p)=que.front();
    //cout<<y<<" "<<x<<" "<<p<<endl;
    que.pop();
    visited[y][x]=true;
    if(chmin(score[y][x],p)){
      rep(i,4){
        ll nx=x+dx4[i],ny=y+dy4[i],np=p+1;
        if(nx==W || nx==-1)continue;
        if(ny==H || ny==-1)continue;
        if(visited[ny][nx])continue;
        if(S[ny][nx]=='#')continue;
        que.push(m_t(ny,nx,np));
      }
    }
  }
  if(visited[H-1][W-1]==false){
    out(-1);
    return 0;
  }
  int need=score[H-1][W-1];
  int white=0;
  for(auto s:S)for(auto e:s)white+=(e=='.');
  
  out(white-need);
  
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=2e3+5;
int a,b,n,stk[N<<1],tp,t[N<<1];
char s[10];

int main(){
	a=read(),b=read();n=a+b;
	if(a<=b)return puts("Impossible"),0;
	REP(i,0,n-1){
		if(!tp){stk[++tp]=i;continue;}
		printf("? %d %d\n",stk[tp],i);
		fflush(stdout);
		scanf("%s",s);
		if(s[0]=='Y')stk[++tp]=i;
		else --tp;
	}
	t[stk[tp]]=1;
	REP(i,0,n-1){
		if(i==stk[tp])continue;
		printf("? %d %d\n",stk[tp],i);
		fflush(stdout);
		scanf("%s",s);
		t[i]=s[0]=='Y';
	}
	printf("! ");
	REP(i,0,n-1)printf("%d",t[i]);
	puts("");
	return 0;
}


Measured memory_bytes: 724
m = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
ans = 0

tmp_sum = sum(a[1:m]) % mod

for x in range(m-1):
  if a[x] % mod != 0:
    ans += (a[x] * tmp_sum) % mod
  
  tmp_sum -= a[x+1] % mod

print(ans%mod)

Measured memory_bytes: 31616
#!/usr/bin/env python3

s = sorted(input())
t = sorted(input(), reverse=True)

ans = ""
for x,y in zip(s,t):
    if x > y:
        ans = "No"
        break
    elif y > x:
        ans = "Yes"
        break

if ans == "":
    if len(s) < len(t):
        ans = "Yes"
    else:
        ans = "No"

print(ans)



Measured memory_bytes: 9132
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
ll n, m, k, ans, mod=1e9+7;
ll dp[101010];
pii p[101010];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll i, j, temp=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>j>>k;
		p[i]=pii(j+k, j-k);
	}
	sort(p+1, p+n+1);
	for(i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];		
		dp[i]=max(dp[i], dp[lower_bound(p+1, p+n, pii(p[i].second, 1e18))-p-1]+1);
	}
	cout<<dp[n];
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char str[maxn],sta[maxn];
bool match(char a,char b){
	return (a == '0' && b == '1') || (a == '1' && b == '0');
}
int main(){
	scanf("%s",str);
	int len = strlen(str);
	int k = -1;
	int cnt = 0;
	for(int i = 0 ; i < len ; ++i){
		if(~k){
			if(match(sta[k],str[i])){
				cnt += 2;
				--k;
			}else{
				sta[++k] = str[i];
			}
		}else{
			sta[++k] = str[i];
		}
	}
	cout<<cnt<<endl;
	return 0;
}

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

typedef long long ll;
vector<int> vi;

int main(){
   double a,b,c,d;
   scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    int diffa=ceil(c/b);
    int diffb=ceil(a/d);
    if(diffa>diffb){
        printf("No");
    }else printf("Yes");

    return 0;
}


Measured memory_bytes: 3812
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int n, m;
    cin >> n >> m;
    if(n==m){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  final static char BLACK = '0';
  final static char WHITE = '1';
 
  public static void main (String[] args) {
    Scanner in = new Scanner(System.in);

    while (in.hasNext()) {
      String S = in.next();

      int whenEvenBlack = 0;
      for (int i = 0; i < S.length(); ++i) {
        if (i % 2 == 0) {
          if (S.charAt(i) != BLACK) {
            ++whenEvenBlack;
          }
        }

        if (i % 2 == 1) {
          if (S.charAt(i) != WHITE) {
            ++whenEvenBlack;
          }
        }
      }
      
      int whenOddBlack = 0;
      for (int i = 0; i < S.length(); ++i) {
        if (i % 2 == 1) {
          if (S.charAt(i) != BLACK) {
            ++whenOddBlack;
          }
        }

        if (i % 2 == 0) {
          if (S.charAt(i) != WHITE) {
            ++whenOddBlack;
          }
        }
      }

      System.out.println(Math.min(whenEvenBlack, whenOddBlack));
    }
  }
}

Measured memory_bytes: 24904
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <string.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

string s;

int main(){
  cin >> s;
  map<char, bool> mp;
  mp['N'] = false;
  mp['W'] = false;
  mp['S'] = false;
  mp['E'] = false;

  REP(i, s.size()) {
    mp[s[i]] = true;
  }

  if((!mp['N'] && mp['S']) || (mp['N'] && !mp['S']) || (!mp['W'] && mp['E']) || (mp['W'] && !mp['E'])) cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 256
package main
import (
    "fmt"
)

func solveMeFirst(a uint32,b uint32) uint32{
    if (a < b) {
        return 0
    } else {
        return a - b
    }
}

func main() {
    var a string
    fmt.Scanf("%v", &a)
    if (a[0] == '9' || a[1] == '9') {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}



Measured memory_bytes: 512
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1, n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

n, W = map(int, input().split())
v = [0]*n
w = [0]*n
for i in range(n):
	v[i], w[i] = map(int, input().split())
print(get_max_value(n, W, v, w))



Measured memory_bytes: 25940
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define BITBOOL(x,a) (((x)>>(a))&1)
int main(){
  string S;int Q,rev=0; queue<char> H,T;
  cin >> S >> Q;
  RPT(i,0,Q){
    int q; cin >> q;
    if(q==1){
      rev = (rev+1)%2;
    }
    else{
      int f; char c; cin >> f >> c;
      if((rev+f)%2==1) H.push(c);
      else T.push(c);
    }
  }
  while(!T.empty()){
    char c = T.front();
    T.pop();
    S+= c;
  }
  reverse(S.begin(),S.end());
  while(!H.empty()){
    char c = H.front();
    H.pop();
    S+= c;
  }
  if(rev==0)reverse(S.begin(),S.end());
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 1152