akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a%=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}
ll fac2[1001][1001];
ll dp[1001][1001];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n,a,b,c,d;
  cin >> n >> a >> b >> c >> d;

  ll fac[n+1];
  fac[0] = 1;
  rep(i,n) fac[i+1] = mu(fac[i],i+1);
  ll inv[n+1];
  rep(i,n+1) inv[i] = dv(1,fac[i]);

  rep(i,n+1)rep(j,n+1) if(i>=j) fac2[i][j] = dv(fac[i],fac[j]);

  rep(i,n+1)rep(j,n+1) dp[i][j] = 0;
  dp[0][0] = 1;
  rep1(i,n){
    rep(j,n+1){
      dp[i][j] = dp[i-1][j];
    }
    if(i<a || b<i) continue;
    rep(j,n+1){
      for(int l = c; l<=d; l++){
        if(j-i*l<0) break;
        ll k = n - (j-i*l);
        // cout << "tot hito kumi res " << k << " " <<  i <<" " << l << " " << endl;
        ll coef = mu(mu(inv[l],pw(inv[i],l)),fac2[k][k-i*l]);
        dp[i][j] = ad(dp[i][j],mu(coef,dp[i-1][j-i*l]));
      }
    }
  }
  cout << dp[n][n] << endl;
  // cout << static_cast<double>(clock()) / CLOCKS_PER_SEC << "s"<<endl;
  
  return 0;
    

}


Measured memory_bytes: 15872
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1000000000;
const double PI = acos(-1);

int main() {
	LL n;
	cin >> n;
	LL ans = 0;
	while (n>1) {
		LL num = n % 3;
		n /= 3;
		if (num)n += 1;
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3108
s = gets.chomp.split('')
count = 0
n = s.size / 2 if s.size.odd?
n = s.size / 2 - 1  if s.size.even?
(0..n).each do |i|
  count += 1 if s[i] != s[s.size - 1 - i]
end
puts count

Measured memory_bytes: 3836
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>


std::string s[2];

struct AA {
	int arr[26];
	AA() { }
	AA(const int(&p)[26]) {
		for (size_t i = 0; i < 26; i++)
		{
			arr[i] = p[i];
		}
	}
	bool operator<(const AA& r)const {
		for (size_t i = 0; i < 26; i++)
		{
			if (arr[i] < r.arr[i]) {
				return true;
			}
			else
				if (arr[i] > r.arr[i]) {
					return false;
				}
		}
		return false;
	}
};
std::set<AA> sumsum;

int n[2];
int sum[2][4001][26];

int main()
{
	using std::cin;

	cin >> s[0] >> s[1];

	n[0] = s[0].size();
	n[1] = s[1].size();
	for (int si = 0; si < 2; si++)
	{
		for (int i = 1; i <= n[si]; i++)
		{
			for (int a = 0; a < 26; a++)
			{
				sum[si][i][a] = sum[si][i-1][a];
				if (s[si][i-1] == a+'a') {
					sum[si][i][a] += 1;
				}
			}
		}
	}
	auto n_min = std::min(n[0], n[1]);
	for (int l = n_min; l >= 0; --l)
	{
		sumsum.clear();
		for (int i = 0; i + l <= n[1]; i++)
		{
			AA tmp;
			for (int a = 0; a < 26; a++)
			{
				tmp.arr[a] = (sum[1][i + l][a] - sum[1][i][a]);
			}
			sumsum.insert(tmp);
		}
		for (int i = 0; i+l <= n[0]; i++)
		{
			AA tmp;
			for (int a = 0; a < 26; a++)
			{
				tmp.arr[a] = (sum[0][i + l][a] - sum[0][i][a]);
			}
			if (sumsum.count(tmp)) {
				std::cout << l << std::endl;
				return 0;
			}
		}
	}
}


#endif



Measured memory_bytes: 4472
n=int(input())
a=list(map(int,input().split()))
total_n=0
cnt_n=0
total_p=0
cnt_p=0

mark=-1
for i in range(n):
    total_n+=a[i]
    if mark<0:
        if total_n>=0:
            cnt_n+=abs(-1-total_n) 
            total_n=-1
    else:
        if total_n<=0:
            cnt_n+=abs(1-total_n)
            total_n=1
    mark*=-1

mark=1
for i in range(n):
    total_p+=a[i]
    if mark<0:
        if total_p>=0:
            cnt_p+=abs(-1-total_p)
            total_p=-1
    else:
        if total_p<=0:
            cnt_p+=abs(1-total_p)
            total_p=1
    mark*=-1

print(min(cnt_p,cnt_n))

Measured memory_bytes: 14468
#include <stdio.h>

int main(void)
{

	int money = 0;
	int ans = 0;
	int tmp;
	scanf("%d", &money);

		tmp = money/ 500;
		ans = tmp * 1000;
		money = money - (500 * tmp);
		tmp = money / 5;
		ans = ans + tmp * 5;
		 
		printf("%d\n", ans);
		return 0;
}

		


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

typedef long long ll;

#define REP(i, n) for(int i=0; i<(n); i++)
#define REPS(i, n) for(int i=0; i<=(n); i++)
#define FOR(i, a, b) for(int i=a; i<(b); i++)
#define FORS(i, a, b) for(int i=a; i<=(b); i++)
// for container x
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

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


    int ans = A*X+B*Y;
    REPS(buy_mix, max(X, Y)){
        ans = min(ans, buy_mix*2*C+max(X-buy_mix, 0)*A+max(Y-buy_mix, 0)*B);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import math

###
# main
if(__name__ == '__main__'):
    # input
    a, b, h, m = map(int, input().split(" "))

    h %= 12
    minute = h * 60 + m

    a_rad = (2.0 * math.pi * minute) / (60 * 12)
    b_rad = (2.0 * math.pi * m) / 60

    a_x = a * math.cos(a_rad)
    a_y = a * math.sin(a_rad)
    b_x = b * math.cos(b_rad)
    b_y = b * math.sin(b_rad)

    x = a_x - b_x
    y = a_y - b_y

    ans = math.sqrt(x*x + y*y)

    print(ans)

# else:
    # do nothing

Measured memory_bytes: 9580
#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int N, M,X[100000];
  int dif[100000],sum = 0;

  scanf("%d %d", &N, &M);
  for (int i = 0; i < M; i++) scanf("%d", &X[i]);
  sort(X, X + M);
  for (int i = 1; i < M; i++) dif[i - 1] = X[i] - X[i - 1];
  sort(dif, dif + (M - 1));
  for (int i = 0; i < M - 1 - (N - 1); i++) sum += dif[i];
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
	int n,a[1005],b[1005],t=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		t=t+b[i]-a[i]+1;
	}
	cout<<t<<endl;
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
result = max(a)
left = 1
right = result
med = left + (right - left) // 2
while left <= right:
    counter = sum([(x - 1) // med for x in a])
    if counter <= k:
        result = med
        right = med - 1
    else:
        left = med + 1
    med = left + (right - left) // 2
print(result)

Measured memory_bytes: 220288
import sys
sys.setrecursionlimit(10 ** 7)

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

color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    if color.count(a) == 0:
        print(0)
        exit()
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)


Measured memory_bytes: 13964
#include <cstdio>
#include <algorithm>
#define reg register
#define min(_a,_b) (_a<_b?_a:_b)
#define max(_a,_b) (_a>_b?_a:_b)
#define reg register
struct node{
	int x,y;
}q[200002];
int R()
{
	reg int x=0;reg char ch=getchar_unlocked();
	for(;ch<48||ch>57;ch=getchar_unlocked());
	for(;ch>=48&&ch<=57;ch=getchar_unlocked()) x=x*10+ch-48;
	return x;
}
bool cmp(reg node i,reg node j)
{
	return i.x<j.x;
}
int main()
{
	reg int n=R(),i,max1=-1,max2=-1,min1=999999999,min2=999999999,k;
	reg long long ans,s;
	for(i=1;i<=n;++i) {
		q[i]=(node){R(),R()};
		if(q[i].x>q[i].y) std::swap(q[i].x,q[i].y);
		max1=max(max1,q[i].x),min1=min(min1,q[i].x);
		max2=max(max2,q[i].y),min2=min(min2,q[i].y);
	}
	ans=(long long)(max1-min1)*(max2-min2);
	std::sort(q+1,q+1+n,cmp);
	s=max2-min1;
	max1=q[n].x,min1=k=999999999;
	for(i=1;i<n;++i) {
		max1=max(max1,q[i].y),min1=min(min1,q[i].y);
		k=min(k,max1-min(min1,q[i+1].x));
	}
	printf("%lld",min(ans,s*k));
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int G[110][110];
int dijkstra(int N , int start , int goal){
    vector <int> used(N,false);
    vector <int> dist(N,1e9);
    dist[start] = 0;
    while(1){
        int V = -1;
        for(int i = 0; i < N; i++)
            if(used[i] == 0 && (V == -1 || dist[V] > dist[i]))
                V = i;
        if(V == -1)
            break;
        used[V] = true;
        for(int i = 0; i < N; i++)
            dist[i] = min(dist[i] , dist[V] + G[V][i]);
    }
    return dist[goal];
}
int main(){
	int n , k;
	while(cin >> n >> k , n){
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				G[i][j] = (i == j ? 0 : 1e9);
		int a , b , c , d, e;
		for(int i = 0; i < k; i++){
			int va;
			cin >> va;
			if(va){
				cin >> c >> d >> e;
				c--; d--;
				G[c][d] = G[d][c] = min(e , G[c][d]); 
			}
			else{
				cin >> a >> b;
				a--; b--;
				cout << (dijkstra(n, a , b) == 1e9 ? -1 : dijkstra(n , a , b)) << endl;
			}
		}
	}
}

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

typedef long long int lli;

int a[3], m[3];

lli gcd(lli a, lli b) {
  if(b == 0) return a;
  return gcd(b, a%b);
}

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

void solve() {
  int t[3];
  lli T[3];
  fill(t, t+3, 1);
  fill(T, T+3, 0);
  for(lli i = 1; ; ++i) {
    for(int j = 0; j < 3; ++j) {
      if(T[j]) continue;
      t[j] = a[j]*t[j] % m[j];
      if(t[j] == 1) T[j] = i;
    }
    if(T[0] && T[1] && T[2]) break;
  }

  cout << lcm(lcm(T[0], T[1]), T[2]) << endl;
}

main() {
  while(1) {
    bool allzero = true;
    for(int i = 0; i < 3; ++i) {
      cin >> a[i] >> m[i];
      if(a[i] != 0 || m[i] != 0) allzero = false;
    }
    if(allzero) break;
    solve();
  }
}

Measured memory_bytes: 0
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		n: usize,
	}

	println!("{}", (1000 - (n % 1000)) % 1000);
}



Measured memory_bytes: 2136
# include<iostream>
# include<vector>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll N = 13;
const ll MOD = 1000000007;
ll dp[100010][13];
int main() {
    string s;
    cin >> s;
    int n = s.length();
    dp[0][0] = 1;
    for (ll i=0; i<n; i++) {
        if (s[i] == '?') {
            for (ll j=0; j<10; j++) {
                for (ll k=0; k<N; k++) {
                    dp[i+1][(k*10+j) % 13] += dp[i][k];
                    dp[i+1][(k*10+j)%13] %= MOD;
                }
            }
        } else {
            ll j = s[i] -'0';
            for (ll k=0; k<N; k++) {
                dp[i+1][(k*10+j) % 13] += dp[i][k];
                dp[i+1][(k*10+j)%13] %= MOD;
            }
        }
    }
    cout << dp[s.length()][5] << endl;
    return 0;
}

Measured memory_bytes: 10624
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

int main (){
  ll n;
  cin>>n;
  if(n==1){
    cout<<1<<endl;
    return 0;
  }
  vector<ll>c(n,0);
  for(ll i=0;i<n;i++){
    cin>>c[i];
    c[i]--;
  }
  vector<ll>dp(n,0);
  vector<ll>v(n,0);
  vector<ll>vv(n,-1);
  dp[n-1]=1;
  v[c[n-1]]=1;
  vv[c[n-1]]=n-1;
  for(ll i=n-2;i>=0;i--){
    if(v[c[i]]==0||vv[c[i]]-i==1){
      dp[i]=dp[i+1];
      v[c[i]]=dp[i];
    }
    else{
      dp[i]=dp[i+1]+v[c[i]];
      v[c[i]]=dp[i];
    }
    vv[c[i]]=i;
    dp[i]%=MOD;
    v[c[i]]%=MOD;
  }
  cout<<dp[0]<<endl;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long 
#define pb push_back
#define fo(i,N) for(int i = 0 ; i < N ; i++)
#define foo(i,x,N) for (int i = x; i < N ; i++)
#define fill(a,val) memset(a,val,sizeof(a))
#define fastio()  ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define ff first
#define ss second
#define MAX 1234567
#define pii pair<int,int> 
#define pll pair<ll,ll> 
#define inf 1e9+1
#define all(a) a.begin(),a.end()

double dp[301][301][301];
vector <int> p(301);
int n;

double solve(int x,int y, int z)
{
  if ( x < 0 || y < 0 || z < 0 )
    return 0;

  if ( x == 0 && y == 0 && z == 0)
    return 0;

  if ( dp[x][y][z] > -0.9)
    return dp[x][y][z];


  dp[x][y][z] = n+ x*solve(x-1,y,z)+ y*solve(x+1,y-1,z) + z*solve(x,y+1,z-1);
  dp[x][y][z] /= (x+y+z);

  return dp[x][y][z];

}

int main()
{  
   cin >> n;
   int x=0,y=0,z=0;
   foo(i,1,n+1)
   { 
    cin >> p[i];
    if ( p[i] == 1)
      x++;
    else if ( p[i] == 2)
      y++;
    else
      z++;
   }

   fill(dp,-1);
   
   // /cout << x << " " << y << " " <<  z << endl;
   cout << fixed << setprecision(10) << solve(x,y,z) << endl;
}



Measured memory_bytes: 213376
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

void makePrimeNumber(int N, vector<bool>& prime) // 0ツ暗按湘」Nツ暗按可コツづ個青ョツ青板つゥツづァツ素ツ青板づーツ探ツつキ
{
    prime.assign(N+1, true);
    prime [0] = prime[1] = false;
    for(int i=2; i*i<=N; i++){
        if(prime[i]){
            for(int j=i; i*j<=N; j++){
                prime[i*j] = false;
            }
        }
    }
}

int main()
{
    vector<bool> prime;
    makePrimeNumber(1299709, prime);

    for(;;){
        int k;
        cin >> k;
        if(k == 0)
            return 0;

        if(prime[k]){
            cout << 0 << endl;
            continue;
        }

        int i = k;
        int j = k;
        while(!prime[i])
            -- i;
        while(!prime[j])
            ++ j;
        cout << (j-i) << endl;
    }
}

Measured memory_bytes: 0
# include "iostream"
# include "cstdio"

using namespace std;

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a+b==15){
		printf("+"); 
	}else if(a*b==15){
		printf("*");
	}else{
		printf("x");
	} 
	return 0;
}

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

using i64 = long long int;

int main(){
    i64 a, b, c, k;
    cin >> a >> b >> c >> k;
    i64 diff = (k % 2 ? b-a : a-b);
    if(abs(diff) > 1000000000000000000)cout << "Unfair" << endl;
    else cout << diff << endl;

    return 0;
}


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

#define MOD 998244353

#define int long long

signed main(){
    int n;
    cin >> n;

    int a[100010];
    int cnt[100010] = {};
    for(int i = 0;i < n;i++){
        cin >> a[i];
        cnt[a[i]]++;
    }

    if(a[0] != 0 || cnt[0] != 1){
        cout << 0 << endl;
        return 0;
    }

    int ans = 1;
    for(int i = 1;i < n;i++){
        ans *= cnt[a[i]-1];
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
	int r,c;
	cin >> r >> c;
	int a[105][105]={0};
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			int num;
			cin >> num;
			a[i][j]=num;
		}
		for(int j=1;j<=c;j++){
			a[i][c+1]+=a[i][j];
		}
	}
	for(int i=1;i<=c+1;i++){
		for(int j=1;j<=r;j++){
			a[r+1][i]+=a[j][i];
		}
	}
	for(int i=1;i<=r+1;i++){
		for(int j=1;j<=c+1;j++){
			if(j!=c+1) cout<<a[i][j]<<" ";
			else cout<<a[i][j]<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3136
_,*a=open(0).readlines()
if len(set(a))<len(a):
  print("No")
  exit()
b=[(i[0],i[-2]) for i in a]
for k in range(len(b)-1):
  if b[k][1]!=b[k+1][0]:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a,b,c,d;

int main()
{
    while (scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        if (a+b==c+d) puts("Balanced");
        else if (a+b>c+d) puts("Left");
        else puts("Right");
    }
    return 0;
}



Measured memory_bytes: 128
#!/usr/bin/env python3
n, l = map(int, input().split())
ans = 0
m = 10**5
for i in range(n):
    if abs(l + i) < m:
        m = abs(l + i)
        ans = l + i
print(n * l + n * (n - 1) // 2 - ans)


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

class Main {
    static char[] a, b, c;
    static int[] ids;
    static char res;
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ids = new int[3];
        a = br.readLine().toCharArray();
        b = br.readLine().toCharArray();
        c = br.readLine().toCharArray();
        recur(0, a);
        System.out.println(res);
    }
    
    static void recur(int id, char[] carr){
        if(ids[id]==carr.length){
            res = (char)(id+'A');
            return;
        }
        char curr = carr[ids[id]];
        ids[id]++;
        if(curr == 'a')
            recur(0, a);
        else if(curr == 'b')
            recur(1, b);
        else
            recur(2, c);
    }
}

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

const int N = pow(10,5);

vector<bool> isp(N+1, true);

void sieve() {
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=N; i++) {
    if (isp[i]) for(int j=2; i*j<=N; j++) isp[i*j] = false;
  }
}

int main() {
  string s;
  int counter=0;
  cin>>s;
  for(int i=0; i<4;i++){
  if(s.at(i)=='+')
  counter++;
  else
  counter--;}
  cout<<counter<<endl;}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int main(){
int H,W ;

while(1){
     cin >> H >> W;
     if(H == 0 && W == 0){
         break;
     }

     for(int j = 0; j< H; j++){
          for(int i = 0; i< W; i++){
               if(j==0 || j==H-1){
                    cout << '#';
               }else{
                    if(i==0 || i==W-1){
                         cout << '#';
                    }else{
                         cout << '.';
                    }
               }
          }
          cout << endl;
     }
     cout << endl;
}
return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
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; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main(){
    int n,a,b;cin >> n >> a >> b;
    cout << min(n*a,b) <<endl;

    return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>

template <typename CommutativeMonoid> class FenwickTree {
	using uint32 = std::uint_fast32_t;

public:
	using value_type = CommutativeMonoid;
	using reference = value_type &;
	using const_reference = const value_type &;

private:
	using F = std::function<value_type(const_reference, const_reference)>;
	const value_type neutral_;
	const F f;
	const uint32 size_;
	std::vector<value_type> tree;
	static uint32 getsize(const uint32 size) {
		uint32 ret = 1;
		while (ret < size)
			ret <<= 1;
		return ret;
	}

public:
	FenwickTree(const uint32 size, const_reference neutral = value_type(),
		const F &f = std::plus<value_type>())
		: neutral_(neutral), f(f), size_(getsize(size)),
		tree(size_ + 1, neutral_) {}
	void update(uint32 index, const_reference diff) {
		assert(index < size_);
		for (++index; index <= size_; index += index & ~index + 1)
			tree[index] = f(tree[index], diff);
	}
	value_type range(uint32 end) const {
		assert(end <= size_);
		value_type ret = neutral_;
		do
			ret = f(tree[end], ret);
		while (end &= end - 1);
		return ret;
	}
	uint32 search(const std::function<bool(const_reference)> &b) const {
		if (!b(tree[size_]))
			return size_;
		uint32 i = 0, k = size_;
		value_type acc = neutral_;
		while (k >>= 1)
			if (!b(f(acc, tree[i + k])))
				acc = f(acc, tree[i += k]);
		return i;
	}
};

#include <iostream>
int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n,q;
	std::cin >>n>> q;
	FenwickTree<int> T(n, 0);
	while (q--) {
		int t, x,y;
		std::cin >> t >> x>>y;
		if (t == 1) {
			std::cout << T.range(y)-T.range(x-1) << "\n";
		}
		else {
			T.update(x-1, y);
		}
	}
	return 0;
}


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

int main(){

    while(1){
        int n;
        cin >> n;
        if(n == 0){
            break;
        }

        vector<int> s(n);
        for(int i = 0; i < n; i++){
            cin >> s[i];
        }

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

        int sum = accumulate(s.begin(), s.end(), 0);

        sum -= (s[0] + s[n - 1]);

        int ans = sum / (n - 2);
        cout << ans << endl;
    }

    return 0;
}


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

int main() {
  int n;
  string s;
  cin >> n >>s;
  int sum = 0;
  for(int i = 0;i < s.size();i++) {
    if (s[i] == 'A' && (s[i+1] == 'B' && s[i+2] == 'C')) {
      sum++;
    }
  }
  cout << sum <<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"

using namespace std;
using ll=long long;
using ull=unsigned long long;

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()

int n,k,a[110];
ll dp[110][100010];

void input(){
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	return;
}

void solve(){
	for(int i=0;i<=n;i++)dp[i][0]=1;
	for(int i=0;i<n;i++){
		for(int j=1;j<=k;j++){
			if(j-1-a[i]>=0){
				dp[i+1][j]=(dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+MOD)%MOD;
			}
			else{
				dp[i+1][j]=(dp[i+1][j-1]+dp[i][j])%MOD;
			} 
		}
	}
	cout<<dp[n][k]<<endl;
	return;
}

int main(){
	input();
	solve();
	return 0;
}

Measured memory_bytes: 79360
# https://atcoder.jp/contests/abc166/tasks/abc166_e

"""
変数分離すれば互いに独立なので、
連想配列でO(N)になる。
"""


import sys
input = sys.stdin.readline
from collections import Counter

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

P = (j+1-A[j] for j in range(N))
M = (i+1+A[i] for i in range(N))

dic = Counter(P)

res = 0
for m in M:
    res += dic.get(m,0)

print(res)

Measured memory_bytes: 122148
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	sum := 0.0
	for i := 0; i < n; i++ {
		var x float64
		var u string
		fmt.Scan(&x,&u)

		if u == "JPY" {
			sum += x
		} else {
			sum += 380000 * x
		}
	}
	fmt.Println(sum)
}

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

struct UnionFind
{
 vector<int> par;
 vector<int> rank;
 vector<int> size;
 int n;

 UnionFind(int N){
     n=N;
     par.resize(n);
     rank.resize(n);
     size.resize(n);
     for(int i=0;i<n;i++){
         par[i]=i;
         rank[i]=0;
         size[i]=1;
     }
 }

 int find_set(int u)
 {
  if(u==par[u]) return u;
  par[u]=find_set(par[u]);
  return par[u];
 }

 bool same(int u,int v)
 {
  return find_set(u)== find_set(v);
 }

 void unite(int u,int v)
 {
  u=find_set(u);
  v=find_set(v);

  if(u==v){
      return;
  }
  if (rank[u]>rank[v]){
      par[v]=u;
      size[u]+=size[v];
  }
  else{
      par[u]=v;
      size[v]+=size[u];
      if(rank[u]==rank[v]){
          rank[v]++;
      }
  }
 }

 void update_par(void)
 {
  for(int i=0;i<n;i++){
      find_set(i);
  }
 }

 int get_size(int u)
 {
  return size[find_set(u)];
 }

}; 

int main()
{
 int n,m; cin >> n >> m;
 int ans=0;
 vector<pair<int,int>> Edges;
 for(int i=0;i<m;i++){
     int u,v; cin >> u >> v;
     u-=1;
     v-=1;
     pair<int,int> e=make_pair(u,v);
     Edges.push_back(e);
 }
 for(int i=0;i<m;i++){
     UnionFind uf(n);
     for(int j=0;j<m;j++){
         if(i!=j){
             pair<int,int> e=Edges[j];
             uf.unite(e.first,e.second);
         }
     }
     if(uf.get_size(0)!=n) ans++;
 }
 cout << ans << endl;
 return 0;
}

Measured memory_bytes: 256
// AtCoder Regular Contest 071
// E - TrBBnsformBBtion

#include <cstdio>
#include <cstring>
#define P 5
#define MAX_S 100000
using namespace std;
typedef long long int ll;


char S[2][MAX_S + 2];
int L[2], sum_a[2][MAX_S + 1];
int Q;


int main() {

  int a, b, c, d;

  scanf("%s", &S[0]);
  scanf("%*c%s", &S[1]);
  for (int j = 0; j < 2; j++) {
    L[j] = strlen(S[j]);
    sum_a[j][0] = 0;
    for (int i = 1; i <= L[j]; i++) {
      sum_a[j][i] = sum_a[j][i - 1] + (S[j][i - 1] == 'A' ? 1 : 0);
    }
  }

  scanf("%d", &Q);
  for (int q = 0; q < Q; q++) {
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if ( ((b - a + 1 - 2 * (sum_a[0][b] - sum_a[0][a - 1])) - (d - c + 1 - 2 * (sum_a[1][d] - sum_a[1][c - 1]))) % 3 == 0 ) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }


  return 0;

}



Measured memory_bytes: 1536
S = input()
N = len(S)

bc = S.count('B')

bpos = 0
ans = 0
for i, si in enumerate(S):
    if si == 'B':
        bpos += 1  # 何個目のbか
        after_pos = N - bc + bpos - 1
        diff = after_pos - i
        ans += diff
        # print('diff', diff, after_pos, bpos)

print(ans)


Measured memory_bytes: 3500
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define fcout(n) cout << fixed << setprecision(n)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acosl(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<pair<int, int>>;
using VTIII = vector<tuple<int, int, int>>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


double R;


signed main(){
    cin >> R;

    fcout(10) << 2*PI*R << endl;

    return 0;
}

Measured memory_bytes: 3792
<?php
define('MOD', 10 ** 9 + 7);
// 入力
fscanf(STDIN, '%d %d', $n, $blue);

$red = $n - $blue;

// 答え出力用配列
$ans = array_fill(0, $blue, 0);

// 計算
combination($n);
for ($i = 1; $i <= $blue; $i++) {
    // 赤いボールが足りない場合
    if ($i - 1 > $red) break;

    // 赤いボールの並べ方
    $red_pos = $i - 1 + 2; // 赤いボールを置ける場所は青いボールの間と左右
    $red_free = $red - ($i - 1); // 自由に置ける赤いボール（青いボールの間には必ず置く）

    if ($red_pos > 1 && $red_free > 0) {
        $red_comb = combination($red_free + $red_pos - 1, $red_pos - 1);
    } else {
        $red_comb = 1;
    }
    // 青いボールの並べ方
    $blue_pos = $i;
    if ($blue_pos > 1 && $blue > 1) {
        $blue_comb = combination($blue - 1, $blue_pos - 1);
    } else {
        $blue_comb = 1;
    }

    // 全てのボールの並べ方
    $ans[$i - 1] = ($red_comb * $blue_comb) % MOD;
}

// 出力
foreach ($ans as $v) echo $v.PHP_EOL;

function combination($n, $m = 0){
    static $pascal;
    if(!isset($pascal)){
        $pascal[0][0] = 1;
        for($j = 1; $j <= $n; $j++){
            for($i = 0; $i <= $j; $i++){
                $pascal[$j][$i] = (($pascal[$j-1][$i-1] ?? 0) + ($pascal[$j-1][$i] ?? 0)) % MOD;
            }
        }
    }
    return $pascal[$n][$m];
}

Measured memory_bytes: 96760
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset
 
using namespace std;
 
typedef long long Lint;
typedef pair<Lint,Lint> ii;
typedef pair<int,char> ic;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;
 
const int maxn = 1020;
const int maxm = 10000020;
const int MOd = 998244353;

int a,b, c;
string s, s2;

void solve() {
	scanf("%d %d %d",&a,&b,&c);
	if( a <= b*c ) printf("Yes\n");
	else printf("No\n");
}
 
int main() {
	int n = 1;
	// scanf("%d",&n);
	while( n-- ) solve();
 
	return 0;
}

Measured memory_bytes: 3760
#include <iostream>

using namespace std;

long long int A, B, C;
long long int boxA, boxB;
long long int ans=0;

int main() {
	cin >> A >> B >> C;
	while (1) {
		if (ans == 0) {
			if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1) {
				break;
			}
		}
		ans++;
		if (2*A==B+C && 2*B==C+A && 2*C==A+B) {
			cout << -1 << endl;
			return 0;
		}
		boxA = A;
		boxB = B;
		A = B / 2 + C / 2;
		B = C / 2 + boxA / 2;
		C = boxA / 2 + boxB / 2;
		if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1) {
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 100001;
static const ll MOD = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool int_ceil(T a, T b) { T res = a / b; if(a % b != 0) res++; return res; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif

int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	int N; cin >> N;

	if(N == 3){
		cout << 2 << endl;
		cout << 1 << " " << 3 << endl;
		cout << 2 << " " << 3 << endl;
		return 0;
	}

	vector<pair<int, int> > ans;

	int NN = N - N % 2;

	vector<pair<int, int> > g;
	rep(i, NN / 2){
		g.push_back({i, NN - i - 1});
	}
	rep(i, g.size()){
		rep2(j, i+1, g.size()){
			auto a = g[i];
			auto b = g[j];
			ans.push_back({a.first, b.first});
			ans.push_back({a.first, b.second});
			ans.push_back({a.second, b.first});
			ans.push_back({a.second, b.second});
		}
	}

	if(N % 2 == 1){
		rep(i, N-1){
			ans.push_back({N-1, i});
		}
	}

	cout << ans.size() << endl;
	rep(i, ans.size()){
		cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
	}


	return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
int main(){
  int a,b;
  scanf(" %d  %d",&a,&b);
  if (a < b)
  {
      printf("a < b\n");
  }
  else if (a > b)
  {
      printf("a > b\n");
  }
  else if ( a == b)
  {
      printf("a == b\n");
  }
  return 0;
}


Measured memory_bytes: 2112
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,m,n) for(int i=m;i<n;i++)
#define endre getchar(); getchar();return 0;
double a[15];
string b[15];
signed main() {
	int n;
	cin >> n;
	double ans = 0;
	rep(i, n) {
		cin >> a[i]>>b[i];
		if (b[i] == "JPY")ans += a[i];
		else { ans += a[i] * 380000.0; }
	}
	cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;


int main(){
  int x;
  cin>>x;
  int l=sqrt(x);
  int maxl=0;
  for(int i=1; i<=l; i++){
    for(int j=2; j<=15; j++){
      int z=pow(i, j);
      if(z>x) continue;
      maxl=max(maxl,z);
    }
  }
  cout<<maxl<<en
  RE
}

Measured memory_bytes: 1020
#include <iostream>
using namespace std;
int main(){
	int a[4],b[4];
	while(cin>>a[0]>>a[1]>>a[2]>>a[3]){
		cin>>b[0]>>b[1]>>b[2]>>b[3];
		int hit=0,blow=0;
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				if(a[i] == b[i]){
					hit++;
					break;
				}else if(a[i] == b[j] && i!=j){
					blow++;
					break;
				}
			}
		}
		cout<<hit<<" "<<blow<<endl;
	}
	return 0;
}

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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main()
{
    int N,Q;
    string s;
    cin >> N >> Q >> s;

    vector<pair<int, int> > lr(Q);
    rep(i,Q) cin >> lr[i].first >> lr[i].second;

    vector<int>dp;
    dp.push_back(0);

    rep(i,s.size()-1)
    {
        if(s[i] == 'A' && s[i+1] == 'C') dp.push_back(dp[dp.size()-1] + 1);
        else dp.push_back(dp[dp.size()-1]);
    }
    rep(i,Q)
    {
        cout << dp[lr[i].second-1] - dp[lr[i].first-1] << endl;
    }
}


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

int main (){
    int W,H,N,number1,number2,number3,number4,ans;
    cin >> W;
    cin >> H;
    cin >> N;
    number1 = 0;
    number2 = W;
    number4 = H;
    number3 = 0;
    vector<int> x(N);
    vector<int> y(N);
    vector<int> a(N);
    for(int i = 0;i < N;i++){
        cin >> x.at(i);
        cin >> y.at(i);
        cin >> a.at(i);
        if(a.at(i) == 1 && number1 <= x.at(i)){
            number1 = x.at(i);
        }
        else if(a.at(i) == 2 && number2 >= x.at(i)){
            number2 = x.at(i);
        }
        else if(a.at(i) == 3 && number3 <= y.at(i)){
            number3 = y.at(i);
        }
        else if(a.at(i) == 4 && number4 >= y.at(i)){
            number4 = y.at(i);
        }
        else{
        }
    }
    if(number1 > number2|| number3 > number4){
        ans = 0;
    }
    else{
        ans = (W - (W - number2 + number1)) * (H-(H-number4 + number3));
    }
    cout << ans << endl;
}
                
         

Measured memory_bytes: 256
def main():
    n = int(input())
    res = 0
    for (a, k) in [map(int, input().split()) for _ in range(n)]:
        while a >= k:
            m = a // k
            if a % k == 0:
                res ^= m
                break
            x = (a - k * m - 1) // (m + 1)
            a -= max(1, x) * (m + 1)
    print('Takahashi' if res != 0 else 'Aoki')


if __name__ == '__main__':
    main()

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

using namespace std;

int main(int argc, const char *argv[]) {
  string s;
  cin >> s;

  int acc = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '+') {
      acc++;
    } else {
      acc--;
    }
  }

  cout << acc << '\n';
  return 0;
}

Measured memory_bytes: 3572
for i in range (1,10):
    print("{}x{}={}".format(i,1,i*1))
    print("{}x{}={}".format(i,2,i*2))
    print("{}x{}={}".format(i,3,i*3))
    print("{}x{}={}".format(i,4,i*4))
    print("{}x{}={}".format(i,5,i*5))
    print("{}x{}={}".format(i,6,i*6))
    print("{}x{}={}".format(i,7,i*7))
    print("{}x{}={}".format(i,8,i*8))
    print("{}x{}={}".format(i,9,i*9))


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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
template <typename T> constexpr T inf = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 4;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define COMP(key) [](const auto& a, const auto& b) { return a.key < b.key; }

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& a) { return is >> a.first >> a.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& a) { for (T& x : a) is >> x; return is; }

void LOG(const int& x) { cerr << x << "\n"; }
template<typename T> void LOG(const vector<T>& a) { for (const T& x : a) cerr << x << " "; cerr << "\n"; }
template<typename T, std::size_t S> void LOG(const T (&a)[S]) { REP(i, S) cerr << a[i] << " "; cerr << "\n"; }
template<typename T, std::size_t S, std::size_t R> void LOG(const T (&a)[S][R]) { REP(i, S) { REP(j, R) cerr << a[i][j] << " "; cerr << "\n"; } }

i64 ceil(i64 a, i64 b) { return (a - 1) / b + 1; }
i64 gcd(i64 a, i64 b) { while (b != 0) { i64 t = b; b = a % b; a = t; } return a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
i64 gcd(const vector<i64>& v) { return accumulate(ALL(v), 1LL, static_cast<i64(*)(i64, i64)>(gcd)); }
i64 lcm(const vector<i64>& v) { return v.empty() ? 0LL : accumulate(v.begin() + 1, v.end(), v[0], static_cast<i64(*)(i64, i64)>(lcm)); }
i64 pow(i64 x, i64 y, i64 z) { i64 a = 1; while (y > 0) { if (y & 1) a = a * x % z; x = x * x % z; y /= 2; } return a; }
i64 inv(i64 x, i64 m) { return pow(x, m - 2, m); }

struct InitCpp { InitCpp() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } initCpp;

const i64 INF = inf<i64>;
using P = pair<i64, i64>;
struct E {
  i64 to;
  i64 cost;
};
signed main() {
  i64 N, M;
  cin >> N >> M;
  vector<vector<E>> G(N);
  REP(_, M) {
    i64 l, r, c;
    cin >> l >> r >> c;
    l--;
    r--;
    G[l].push_back({r, c});
  }
  FOR(i, 1, N) {
    G[i].push_back({i - 1, 0});
  }
  priority_queue<P, vector<P>, greater<P>> que;
  vector<i64> D(N, INF);
  D[0] = 0;
  que.push({0, 0});
  while (que.size()) {
    P p = que.top();
    que.pop();
    if (D[p.second] < p.first) continue;
    for (auto e : G[p.second]) {
      if (D[e.to] > D[p.second] + e.cost) {
        D[e.to] = D[p.second] + e.cost;
        que.push({D[e.to], e.to});
      }
    }
  }
  cout << (D[N - 1] == INF ? -1 : D[N - 1]) << endl;
}


Measured memory_bytes: 9336
#include <bits/stdc++.h>
using namespace std;
using i64=long long;

main()
{
    i64 n,a,b;
    while(1)
    {
        cin>>n>>a>>b;
        if(!n) break;
        a--;
        string op;
        i64 c=1ll<<n;
        for(int i=0;i<n;i++,(++b)/=2)
        {
            if((a&1)==(b&1)) op+='R';
            else op+='L';
            c>>=1;
            // cerr<<"\t"<<a<<" "<<b<<endl;
            if(a<c) a=c-a-1;
            else a-=c;
        }
        reverse(begin(op), end(op));
        cout<<op<<endl;
    }
}



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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;



int n;
string s;
map<string, int> mp;

string strs[4] = {"AC", "WA", "TLE", "RE"};

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

    cin >> n;
    rep(i, 0, n) {
        cin >> s;
        mp[s]++;
    }
    rep(i, 0, 4) {
        cout << strs[i] << " x " << mp[strs[i]] << endl;
    }
}

Measured memory_bytes: 3664
N,M,X = map(int,input().split())
C=[0]*N
A=[[0]*M for i in range(N)]


for i in range(N):
    hon = list(map(int,input().split()))
    C[i]=hon[0]
    for j in range(M):
        A[i][j] = hon[j+1]
rikaido=[0]*M
ans = 20*(10**5)
for i in range(2**N):
    pattern=[0]*N
    temp = 0
    rikaido=[0]*M
    for j in range(N):
        if (i >> j & 1):
            for k in range(M):
                pattern[j] =1
                rikaido[k]+=A[j][k]
            temp+=C[j]
    flag = 0
    for i in range(M):
        if rikaido[i] < X:
            flag = 1
    if flag ==0 and temp < ans:
        ans = temp

if ans == 20*(10**5):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9256
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

struct state{int y,x,cost;};

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int t[50][50][2];
int H,W,a;
bool visited[50][50];

bool inField(int y,int x){
  if(y<0||y>=H)return false;
  if(x<0||x>=W)return false;
  return true;
}
int check(int y,int x,int dir){
  if(dir==0)return t[y-1][x][1];
  if(dir==1)return t[y][x][0];
  if(dir==2)return t[y][x][1];
  if(dir==3)return t[y][x-1][0];
}

void init(){
  for(int i=0;i<50;i++)
    for(int j=0;j<50;j++)visited[i][j]=false;
}

void solve(){
  queue< state >Q;
  Q.push((state){0,0,1});
  while(!Q.empty()){
    state s = Q.front();Q.pop();
    if(visited[s.y][s.x])continue;
    visited[s.y][s.x]=true;
    if(s.y==H-1&&s.x==W-1){cout<<s.cost<<endl;return;}
    for(int i=0;i<4;i++){
      int ny=s.y+dy[i],nx=s.x+dx[i];
      if(!inField(ny,nx))continue;
      if(check(s.y,s.x,i)==1)continue;
      Q.push((state){ny,nx,s.cost+1});
    }
  }
  cout<<0<<endl;
}

int main(){
  while(cin>>W>>H&&W&&H){
    for(int i=0;i<H-1;i++){
      for(int j=0;j<W-1;j++)cin>>t[i][j][0];
      for(int j=0;j<W;j++)cin>>t[i][j][1];
    }
    for(int j=0;j<W-1;j++)cin>>t[H-1][j][0];
    init();
    solve();
  }
  return 0;
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
using namespace std;
struct player
{
	int mark;
}s[100005];

int main()
{
	int n,k,q;
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{

		s[i].mark=k;
	}
	int sum=0;
	for(int i=1;i<=q;i++)
	{
		int x;
		cin>>x;
		s[x].mark++;
		sum++;
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i].mark-sum>0) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
	
}

Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 100000
int A[MAX],n;
int partition(int p,int r)
{
	int x,i,j,t;
	x=A[r];
	i=p-1;
	for(j=p;j<r;j++)
	{
		if(A[j]<=x)
		{
			i++;
			t=A[j];A[j]=A[i];A[i]=t;
		}
	}
	t=A[i+1];A[i+1]=A[r];A[r]=t;
	return i+1;
}
int main()
{
	int i,q;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&A[i]);
	q=partition(0,n-1);
	for(i=0;i<n;i++)
	{
		if(i)printf(" ");
		if(i==q)printf("[");
		printf("%d",A[i]);
		if(i==q)printf("]");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 2916
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

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

  int lb = 0, ub = N;
  while (ub > lb + 1) {
    int mid = (lb + ub) / 2;

    int64_t score = (int64_t)mid * (mid + 1) / 2;
    (score >= N ? ub : lb) = mid;
  }

  const int64_t score = (int64_t)ub * (ub + 1) / 2;
  rep(i, ub) {
    if (score - N != i + 1) {
      cout << i + 1 << "\n";
    }
  }
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
double dp[303][303][303];
int n,cnt[4];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	for(int i=0;i<=300;i++)
		for(int j=0;j<=300;j++)
			for(int k=0;k<=300;k++){
				if(i||j||k){
					if(i+j+k>n)break;
					if(k)dp[k][j][i]+=dp[k-1][j][i]*k;
					if(j)dp[k][j][i]+=dp[k+1][j-1][i]*j;
					if(i)dp[k][j][i]+=dp[k][j+1][i-1]*i;
					dp[k][j][i]=(dp[k][j][i]+n)/(i+j+k);
				}
			}
	printf("%.12lf\n",dp[cnt[1]][cnt[2]][cnt[3]]);
	return 0;
}
/*
10
1 3 2 3 3 2 3 2 1 3
*/

Measured memory_bytes: 217344
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long ll;

int main() {
	int H, W, N;
	int sr, sc;
	cin >> H >> W >> N;
	cin >> sr >> sc;
	getchar();
	string s, t;
	getline(cin, s);
	getline(cin, t);
	int position = sc;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'R') position++;
		if (position > W) { cout << "NO" << endl; return 0; }
		if (t[i] == 'L' && position > 1) position--;
	}
	position = sc;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'L') position--;
		if (position < 1) { cout << "NO" << endl; return 0; }
		if (t[i] == 'R' && position <W) position++;
	}
	position = sr;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'U') position--;
		if (position < 1) { cout << "NO" << endl; return 0; }
		if (t[i] == 'D' && position<H) position++;
	}
	position = sr;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'D') position++;
		if (position > H) { cout << "NO" << endl; return 0; }
		if (t[i] == 'U'&& position > 1) position--;
	}
	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 776