akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

d, n = map(int, input().split())

if d == 0 and n == 100:
    print(101)
elif d == 0:
    print(n)

if d == 1 and n == 100:
    print(10100)
elif d == 1:
    print(100 * n)

if d == 2 and n == 100:
    print(1010000)
elif d == 2:
    print(10000 * n)    


Measured memory_bytes: 3060
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read(){
	int f=1,x=0; char c=getchar();
	while (c>'9' || c<'0') {if (c=='-') f=-1; c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
	return f*x;
}
int n,a[201000],b[201000],c[201000],d[201000],sum,ans;
int find(int x){
	int l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(c[mid]>=x)r=mid-1;else l=mid+1;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int k=1;k<=29;k++){
		int x=1<<k,y=1<<(k-1);
		for(int i=1;i<=n;i++){
			c[i]=a[i]&(x-1);
			d[i]=b[i]&(x-1);
		}
		sum=0;
		sort(c+1,c+n+1);
		for(int i=1;i<=n;i++){		
		sum+=find(x-d[i])-find(y-d[i]);
		sum+=n+1-find(x+y-d[i]);		
		}
		if(sum&1)ans+=y;
	}
	cout<<ans;
	return 0;
}

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

long long ans = 1e9;
long long n;
vector<long long> len(3);
// now[i].firstが全長さ、now[i].secondが本数
// 3グループ + 未使用の1グループで構成し、探索中はそれぞれの値が常に変動する
vector<pair<long long, long long>> now(4, pair<long long, long long>(0, 0));

// それぞれの竹について深さ優先探索
void dfs(long long depth, vector<long long> &l) {
    if (depth < n) {
        for (int i=0; i<4; i++) {
            now[i].first += l[depth];
            now[i].second++;
            dfs(depth+1, l);
            now[i].first -= l[depth];
            now[i].second--;
        }
    } else {
        long long tmp = 0;
        for (int i=0; i<3; i++) {
            if (now[i].second == 0) return;
            tmp += abs(len[i] - now[i].first) + (now[i].second - 1) * 10;
        }
        ans = min(ans, tmp);
    }
}

void solve(long long N, long long A, long long B, long long C, std::vector<long long> l){
    n = N;
    len[0] = A;
    len[1] = B;
    len[2] = C;
    
    dfs(0, l);
    cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    std::vector<long long> l(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&l[i]);
    }
    solve(N, A, B, C, std::move(l));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#define rep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
typedef long long int lli;
using namespace std;
int main(){
  int a,b,ans=1;
  cin>>a>>b;
  if(b==1){
    cout<<0<<endl;
    return 0;
  }
  rep(i,1,b){
    //cout<<ans<<' ';
    if(b<=ans+a-1){
      cout<<i<<endl;
      break;
    }
    ans+=a-1;
  }
  return 0;
}

Measured memory_bytes: 256
/*#include <iostream>
#include <bits/stdc++.h>
#define fast_cin ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mp make_pair
#define ll long long int
using namespace std;

vector<ll> dp(100005,0);
int m=1e9+7;
bool cmp(pair<int,int>&a,pair<int,int>&b)
{
    if(a.second==b.second)
        return a.first<b.first;
    else
        return a.second<b.second;
}

bool cmp_(pair<int,pair<int,int> >&a,pair<int,pair<int,int> >&b)
{
   return a.second.first<b.second.first;
}

void factorial()
{
    dp[1]=1;
    for(int i=2;i<=100000;i++)
    {
        dp[i]=((dp[i-1]%m)*(i%m))%m;
    }
}

int main()
{
    fast_cin;
      string s,t;
      cin>>s>>t;
      int n=s.length();
      int m=t.length();
      unsigned int dp[n+1][m+1];
      string ans;
      for(int i=0;i<=n;i++)
      {
          for(int j=0;j<=m;j++)
          {
              if(i==0||j==0)
                dp[i][j]=0;
              else if(s[i-1]==t[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
              else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
              /*if(ans.length()<dp[i][j])
                ans+=s[i];
          }
      }
      cout<<dp[n][m]<<endl;
      //cout<<ans<<endl;
    return 0;
}*/
#include <iostream>
#include <bits/stdc++.h>
#define fast_cin ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mp make_pair
#define ll long long int
using namespace std;

vector<ll> dp(100005,0);
int m=1e9+7;
bool cmp(pair<int,int>&a,pair<int,int>&b)
{
    if(a.second==b.second)
        return a.first<b.first;
    else
        return a.second<b.second;
}

bool cmp_(pair<int,pair<int,int> >&a,pair<int,pair<int,int> >&b)
{
   return a.second.first<b.second.first;
}

void factorial()
{
    dp[1]=1;
    for(int i=2;i<=100000;i++)
    {
        dp[i]=((dp[i-1]%m)*(i%m))%m;
    }
}
void binary(int n)
{
    // array to store binary number
    int binaryNum[32];

    // counter for binary array
    int i = 0;
    while (n > 0) {

        // storing remainder in binary array
        binaryNum[i] = n % 2;
        n = n / 2;
        i++;
    }

    // printing binary array in reverse order
    for (int j = i - 1; j >= 0; j--)
        cout << binaryNum[j];
}
int main()
{
    fast_cin;
    string s;
    cin>>s;
    ll n=s.length();
    ll ans=0;
    for(int i=0;i<n;i++)
        ans+=s[i]-'0';
    if(ans%9)
        cout<<"No";
    else
        cout<<"Yes";
    return 0;
}


Measured memory_bytes: 4400
import numpy as np

N, M, X = map(int, input().split())

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n,skill):
  global ans
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  s = skill.copy()
  DFS(n+1,s)
  s = s + ca[n]
  DFS(n+1,s)
  return
#

DFS(0,skill)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Measured memory_bytes: 27156
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {


        static void Main(string[] args)
        {
            double r = double.Parse(Console.ReadLine());

            Console.WriteLine("{0:f6} {1:f6}",
                r * r * Math.PI,
                2 * r * Math.PI
                );

        }
    }
}

Measured memory_bytes: 9344
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string a;
    cin >> a;
    cout << a.substr(0, 3) << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

// #define DEBUG 1
#define DFILE "t1.1"

int main()
{
  int n, m;

#ifdef DEBUG
#define cin fin
  fstream fin(DFILE);
#endif

  int min_n, max_n;
  cin >> n >> m;
  min_n = 1;
  max_n = n;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    min_n = max(min_n, l);
    max_n = min(max_n, r);
  }
  if (min_n <= max_n)
    cout << max_n - min_n + 1 << endl;
  else
    cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
import math
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
S = 0
for i in range(N):
    S+=A[i]
    if S>=math.ceil(L/2):
        break
ans = min(S*2-L, L-(S-A[i])*2)
print(ans)



Measured memory_bytes: 89296
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)

ll gcd(ll, ll);
ll lcm(ll, ll);

int main() {

	int n; cin >> n;

	vector<int> a(n), b(n);
	map<int, int> ab;
	rep(i, 0, n) {
		cin >> a[i] >> b[i];
		ab[b[i]] += a[i];
	}
	
	ll limit = 0, time = 0;

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

	limit = b[0];
	time += ab[b[0]];
	if (time > limit) {
		cout << "No" << endl;
		return 0;
	}

	rep(i, 1, n) {
		if (b[i] != b[i - 1]) {
			limit = b[i];
			time += ab[b[i]];
			if (time > limit) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	cout << "Yes" << endl;

	return 0;
}

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

int64_t MOD = 1000000007;
int64_t MAX = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N;
    cin >> N;
    vector<int> list(N), dp(N);
    for (int i = 0; i < N; i++)
        cin >> list[i];
    dp[1] = abs(list[1] - list[0]);
    for (int i = 2; i < N; i++)
        dp[i] = min(dp[i - 1] + abs(list[i] - list[i - 1]), dp[i - 2] + abs(list[i] - list[i - 2]));
    cout << dp[N - 1];
}

Measured memory_bytes: 4032
#include<iostream>
using namespace std;
int main(){
  int n,w,h,x,y,dis,s,e;
  bool w_f=true,h_f=true;
  int field_w[100001]={},field_h[100001]={};
  cin >> n >> w >> h;
  for(int i=0;i<n;i++){
    cin >> x >> y >> dis;
    s = x - dis;
    e = x + dis;
    if(s<0)s=0;
    if(e>=w)e=w;
    field_w[s]++;
    field_w[e]--;
    s = y - dis;
    e = y + dis;
    if(s<0)s=0;
    if(e>=h)e=h;
    field_h[s]++;
    field_h[e]--;
  }
  if(field_h[0]<=0) h_f=false;
  if(field_w[0]<=0) w_f=false;
  for(int i=1;i<h;i++){
    field_h[i]=field_h[i]+field_h[i-1];
    if(field_h[i]<=0||h_f==false){
      h_f=false;
      break;
    }
  }
  for(int i=1;i<w;i++){
    field_w[i]=field_w[i]+field_w[i-1];
    if(field_w[i]<=0||w_f==false){
      w_f=false;
      break;
    }
  }
  if(w_f||h_f) cout << "Yes\n";
  else cout << "No\n";
}



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

typedef long long ll;
typedef pair<int,int> P;

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    string s; cin >> s;
    int ans=0;
    if(s[0]=='R'&&s[1]=='R'&&s[2]=='R') ans=3;
    else if(s[0]==s[1]&&s[0]=='R') ans=2;
    else if(s[1]==s[2]&&s[1]=='R') ans=2;
    else if(s[0]=='R'||s[1]=='R'||s[2]=='R') ans=1;
    cout << ans << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;using ll=int_fast64_t;using ld=long double;using pll=pair<ll,ll>;using pld=pair<ld,ld>;const ll INF=1LL<<60;
void solve();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);solve();}
#define fi first
#define se second
#define SELECTOR(_1,_2,_3,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b; return 1;} return 0;}
template<class T> void contout(const T &v){for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n"))cout<<*it;}

template<class T,class F>
T bisection(T l,T r,F f,bool left=true,bool discrete=true){
  T eps=discrete?1:pow(10,-12);
  if((!left)^f(r)) return left?r:r+1;
  if(left^f(l)) return left?l-1:l;
  while(r-l>eps){
    T h=(l+r)/2;
    if((!left)^f(h)) l=h;
    else r=h;
  }
  return discrete?(left?l:r):(l+r)/2;
}

void solve(){
  ll n,k; cin>>n>>k;
  vector<ll> A(n);
  rep(i,n) cin>>A[i];
  sort(A.begin(),A.end());

  auto check=[&](ll x){
    vector<ll> dp(k,0);
    dp[0]=1;
    rep(i,n){
      if(i==x) continue;
      vector<ll> newdp=dp;
      ll a=A[i];
      rep(j,k){
        if(j+a<k) newdp[j+a]=max(dp[j+a],dp[j]);
      }
      dp=newdp;
    }
    return *max_element(dp.begin()+max((ll)0,k-A[x]),dp.end());
  };
  cout<<bisection((ll)0,n-1,check,false)<<"\n";
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
    ll N, K; cin >> N >> K;
    ll ans = 0;
    if(N > K) {
        ll b = N - (K * (N / K));
        ans = min(abs(b), abs(b - K));
    } else if(N <= K) {
        ans = min(N, abs(N - K));
    }
    cout << ans << endl;
}

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

class Dice {
public:
	int		value  = 1;                    // 上面の値　
	int 	s[7] = {0, 1, 2, 3, 4, 5, 6};  // 各面の値

	void init(int x[]) {
		for(int i=0; i<6; i++ ) s[i+1] = x[i];
		for(int i=0; i<6; i++ ) v[i+1] = x[i];
		value = s[1];	
	}	 
	
	void init() {
		for(int i=0; i<7; i++ ) s[i] = v[i];
		value = s[1];	
	}	 
	
	
	void dump() {
		for(int i=1; i<=6; i++) {
			cout << "S" << i << ":" << s[i] <<", ";
		}
		cout << endl;
	}	
		
	void flip(char c) {
		switch (c) {
			case 'N':
				flip_N();
				break;
			case 'S':
				flip_S();
				break;
			case 'E':
				flip_E();
				break;
			case 'W':
				flip_W();
				break;
			default:
				break;
		}
	}
	void flips(string cmds) {
		for(int i=0; i<cmds.size(); i++) {
			flip(cmds[i]);
		}	
	} 	
	
	int flip_N() {
		// 面3,4変わらず、面1265 をローテ―トする(x軸ロテーション)
		int x = s[1];
		s[1] = s[2];
		s[2] = s[6];
		s[6] = s[5];
		s[5] = x;

		value  = s[1];
	}
	
	int flip_S() {
		// 面3,4変わらず、面1265 をローテ―トする(x軸ロテーション)
		int x = s[1];
		s[1] = s[5];
		s[5] = s[6];
		s[6] = s[2];
		s[2] = x;

		value  = s[1];
	}
	
	int flip_E() {
		// 面2,5変わらず、面1364 をローテ―トする(y軸ロテーション)
		int x = s[1];
		s[1] = s[4];
		s[4] = s[6];
		s[6] = s[3];
		s[3] = x;

		value  = s[1];
	}

	int flip_W() {
		// 面2,5変わらず、面1364 をローテ―トする(y軸ロテーション)
		int x = s[1];
		s[1] = s[3];
		s[3] = s[6];
		s[6] = s[4];
		s[4] = x;

		value = s[1];
	}

	int rotate_z() {
		// 面1固定で縦軸(z軸)回転
		int x = s[2];
		s[2] = s[4];
		s[4] = s[5];
		s[5] = s[3];
		s[3] = x;
	}

	bool same_dice(Dice d2) {
		string command = "NNWWNW";   
		bool found = false;
		for(int j=0;j<command.size(); j++) {
			d2.flip(command[j]);

			if ( s[1] == d2.s[1] ) { // 上面を合わせる
				for(int k=0; k<4; k++) {
					d2.rotate_z();
					if (same(d2)) {
						found = true;            
						goto loop_exit;
					}
				}	
			}		
		}
		loop_exit:
		return found;
	}
		

private:
	int 	v[7] = {0, 1, 2, 3, 4, 5, 6};  // 各面の初期値

	bool same(Dice d2) {
		bool rtn = true;
		for (int i=0; i<=6; i++) {
			if ( s[i] != d2.s[i] ) {
				rtn = false;
				break;
			}
		}
		return rtn;
	}
};




int main() {
	int n;
	cin >> n;
	
	int s[6];
	Dice d[n];
	
	for(int i=0; i<n; i++)  {
		for(int j=0;j<6;j++) 
			cin >> s[j];
		d[i].init(s);
	}
	
	string are_same = "Yes";
	for(int i=0; i<n; i++) {
		for(int j=i+1; j<n; j++) {
			if (d[i].same_dice(d[j])) {
//				cout << "d[" << i << "] and d[" << j << "] are same." << endl;
				are_same = "No";
				goto loop_exit;
			} else {
//				cout << "d[" << i << "] and d[" << j << "] are not same." << endl;
			}	
		}
	}
	loop_exit:
	cout << are_same << endl;
	
	return 0;
}


Measured memory_bytes: 3232
#include<stdio.h>

int A[2000001];

void CountingSort(int n){
  int k=10000,i,j,B[2000001],C[10001];
  for(i=0;i<k;i++)
    C[i]=0;
  for(j=0;j<n;j++){
    C[A[j]]++;
  }

  for(i=1;i<k;i++)
    C[i] = C[i] + C[i-1];
  
  for(j=n-1;j>=0;j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  for(i=1;i<n;i++)
    printf("%d ",B[i]);
  printf("%d\n",B[n]);
}
 
main(){
  int i,n;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  CountingSort(n);
  return 0;
}

Measured memory_bytes: 16260
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < (n); i++)

using namespace std;

void solve() {
  long N;
  cin >> N;

  long aaa = 1;
  while (true) {
    long tmp = aaa * (aaa+1) / 2;
    if (tmp >= N) break;
    aaa++;
  }

  long foo = aaa * (aaa+1) / 2;
  long bar = foo - N;

  for (long i = 1; i <= aaa; i++) {
    if (i != bar) cout << i << endl;
  }
}

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


Measured memory_bytes: 256
S = input()

s_hash = {}
for i in range(len(S)):
    if S[i] in s_hash:
        s_hash[S[i]] += 1
    else:
        s_hash[S[i]] = 1


for i in s_hash.values():
    if i != 2:
        print("No")
        exit()
print("Yes")

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

int main(){
    int n, m;
    cin >> n >> m;
    int p[110000];
    string s[110000];
    for(int i=0; i<m; i++){
        cin >> p[i] >> s[i];
    }
    bool isAC[110000];   //1オリジン
    for(int i=1; i<=n; i++){
        isAC[i] = false;
    }
    
    int penaCount[110000] = {};
    for(int i=0; i<m; i++){
        if(s[i] == "WA"  &&  !(isAC[p[i]])){
            penaCount[p[i]]++;
        }
        if(s[i] == "AC"){
            isAC[p[i]] = true;
        }
    }


    int ACcount = 0, allPenaCount = 0;
    for(int i=1; i<=n; i++){
        if(isAC[i]){
            ACcount++;
            allPenaCount += penaCount[i];
        }
    }
    cout << ACcount << " " << allPenaCount << endl;
    return 0;
}

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

#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define All(x) x.begin(), x.end()
#define louisfghbvc int t; cin >> t; while(t--)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<LL> vi;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << "\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

const int K = 1e5+5;
int arr[105];
int dp[K];
int n, k;

int dfs(int remain){
    if(dp[remain] != -1) return dp[remain];
    bool res = 0;
    for(int i = 0; i < n; ++i){
        if(remain >= arr[i]) res |= (dfs(remain-arr[i]) == 0);
    }
    return dp[remain] = res;
}

void solve(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> arr[i];
    memset(dp, -1, sizeof dp);

    cout << (dfs(k)==1 ? "First": "Second") << "\n";
}

int main()
{
    Fast;
    //louisfghbvc{
        solve();
    //}
    return 0;
}


Measured memory_bytes: 8696
s = input().strip()
MOD = pow(10, 9) + 7
# dp: dp[0][...] = ABCカウントを更新しない時の数
# dp: dp[1][...] = Aまで合わせた時の数
# dp: dp[2][...] = Bまで合わせた時の数
# dp: dp[3][...] = Cまで合わせた時の数
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1

for i, _s in enumerate(s):
  if _s == '?':
    dp[0][i+1] += dp[0][i] * 3 % MOD
    dp[1][i+1] += dp[1][i] * 3 % MOD
    dp[2][i+1] += dp[2][i] * 3 % MOD
    dp[3][i+1] += dp[3][i] * 3 % MOD
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  else:
    dp[0][i+1] += dp[0][i]
    dp[1][i+1] += dp[1][i]
    dp[2][i+1] += dp[2][i]
    dp[3][i+1] += dp[3][i]
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  if _s == 'A' or _s == '?':
    dp[1][i+1] += dp[0][i]
    dp[1][i+1] %= MOD
  if _s == 'B' or _s == '?':
    dp[2][i+1] += dp[1][i]
    dp[2][i+1] %= MOD
  if _s == 'C' or _s == '?':
    dp[3][i+1] += dp[2][i]
    dp[3][i+1] %= MOD

print(dp[3][-1])


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

int main()
{
    int a;
    int b;
    int c;
    int d;
    int e;
    int f;
    int g;
    int h;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cin >> e;
    cin >> f;
    cin >> g;
    cin >> h;
    int S = a + b + c + d;
    int T = e + f + g + h;
    vector<int> v{S,T};
    sort(v.begin(),v.end());
    cout << v[1] << endl;
}

Measured memory_bytes: 3120
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	int T; cin >> T;
	while (T--) {
		int a, b; cin >> a >> b;
		cout << (a % 2 ? (b + (a - 1) * 127) : (a * 127 - b)) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));
const ll MOD = 1e9 + 7;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


ll h,w;
vector<string> v(50);

vector<long long> enum_divisors(long long N) {
    vector<long long> res;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // push its partner
            if (N/i != i) res.push_back(N/i);
        }
    }

    sort(res.begin(), res.end());
    return res;
}

int main(){

    ll n,m; cin >> n >> m;
    float nn = n, mm = m;
    vector<ll> a = enum_divisors(m);

    for(int i = a.size()-1; i >= 0; i --){
        if(a[i] - m/n < EPS ){
            cout << a[i];
            return 0;
        }
    }

}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
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; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


int main() {
    long long N, K;
    while (cin >> N >> K) {
        long long res = 0;
        while (N) {
            ++res;
            N /= K;
        }
        cout << res << endl;
    }
}

















Measured memory_bytes: 256
import math
from collections import deque
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq

n = readInt()
k = readInt()
x = readInts()

ans = 0
for i in range(n):
	ans+=min(x[i],abs(x[i]-k))*2
print(ans)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
constexpr long long int mod = 1000000007, MOD = 998244353;
constexpr double PI = 3.14159265358979323846;

int main() {
	int N,ans=0;
	cin >> N;
	vector<int>L(N);
	for (size_t i = 0; i < N; i++)
	{
		cin >> L.at(i);
	}
	sort(L.begin(), L.end(),greater<int>());
	for (size_t i = 0; i < N; i++)
	{
		for (size_t j = i+1; j < N; j++)
		{
			for (size_t k = j+1; k < N; k++)
			{
				if (L.at(i) != L.at(j) && L.at(j) != L.at(k) && L.at(i) < L.at(j) + L.at(k))ans++;
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 3632
N, M, X, Y = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

Z_min = max(x) + 1
Z_max = min(y)

is_ok = False
for Z in range(Z_min, Z_max + 1):
    if X >= Z:
        continue
    if Z > Y:
        continue
    is_ok = True

if is_ok:
    print('No War')
else:
    print('War')


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

int main() {
	long long n, l = 0, ans = 0;
	cin >> n;
	if(n%2==0||n%5==0)cout << "-1\n";
	else{
		do{
			l*=10;l+=7;l%=n;ans++;
		}while(l!=0);
		cout << ans << '\n';
	}
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        a[i] += a[i - 1];
    }
    map<lint, lint> m;
    lint ret = 0;
    m[0]++;
    for (int i = 0; i < n; ++i) {
        ret += m[a[i]];
        m[a[i]]++;
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 14336
# -*- coding: utf-8 -*-

Plot = []

for i in range(5):
    Plot.append(int(input()))

max_distance = int(input())

for i in range(9):
    if(i < 4):
        if(abs(Plot[0] - Plot[i+1]) > max_distance):
            print(":(")
            break
    elif(4 <= i <= 6):
        if (abs(Plot[1] - Plot[i-2]) > max_distance):
            print(":(")
            break
    elif(6 < i < 8):
        if (abs(Plot[2] - Plot[i - 5]) > max_distance):
            print(":(")
            break
    elif(i == 8):
        if(abs(Plot[3] - Plot[4]) > max_distance):
            print(":(")
        else:
            print("Yay!")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    string S;
    cin >> S;
    int cnt[3] = {}, l = (S.size() + 2) / 3;
    for(auto c:S)cnt[c-'a']++;
    if(cnt[0] <= l && cnt[1] <= l && cnt[2] <= l)cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
using namespace std;
double p[3000];
double dp[3000][6000];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i];
	dp[0][3000]=1;
	for(int i=1;i<=n;i++)
		for(int j=-i+3000;j<=i+3000;j++)
			dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j+1]*(1-p[i]);
	double ans=0;
	for(int i=3001;i<=3000+n;i++)
		ans+=dp[n][i];
	printf("%.10lf",ans);
}

Measured memory_bytes: 85596
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <stdio.h>

using size_type = unsigned int;
constexpr size_type N = 1e6 + 20;
char Input[N + 1];
char *input = Input;
bool exist = false;
bool answer[] = {false, false};

int main(void){
    fread(Input, sizeof(char), N, stdin);
    unsigned int n = 0;
    while(*input >= '0') n = 10 * n + (*input++) - '0';
    ++input; const unsigned int m = n - 1;
    for(unsigned int i = 0; i < n; ++i, ++input){
        if(*input == '2'){
            exist = true;
            if((m | i) == m) answer[0] = not answer[0];
        }
        else if(*input == '3'){
            if((m | i) == m) answer[1] = not answer[1];
        }
    }
    if(exist) putchar(answer[0] ? '1' : '0');
    else putchar(answer[1] ? '2' : '0');
    putchar('\n');
    return 0;
}


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

#define ll long long
int n, m, id[101000]; ll a[101000], b[101000], f[101000], sb[101000];
vector<int>G[101000];
int fa[101000], fl[101000];
int GF(int x){
    return fa[x]==x? x: fa[x]=GF(fa[x]);
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i],&b[i]);
        a[i]=max(a[i],b[i])-b[i];
    }
    for (int x,y;m--;){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int i=1;i<=n;++i){
        fa[i]=i; id[i]=i;
    }
    sort(id+1,id+n+1,[](int i,int j){return a[i]<a[j];});
    for (int i=1;i<=n;++i){
        int x=id[i]; fl[x]=1; sb[x]=b[x];
        vector<int>ch;
        for (auto y:G[x]){
            if (!fl[y=GF(y)]) continue;
            if (y==x) continue;
            ch.push_back(y); fa[y]=x;
        }
        for (auto y:ch) sb[x]+=sb[y];
        f[x]=sb[x]+a[x];
        for (auto y:ch) f[x]=min(f[x],sb[x]-sb[y]+max(a[x],f[y]));
        //printf(" %d %lld %lld\n",x,sb[x],f[x]);
    }
    cout<<*max_element(f+1,f+n+1)<<endl;
}

Measured memory_bytes: 10620
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin >> s;
  int N = s.size();

  bool all9 = true;
  for(int i=1;i<N;i++){
    if(s[i] != '9') all9 = false;
  }
  if(all9){
    cout << 9 * (N-1) + s[0] - '0' << endl;
    return 0;
  }

  cout << (N-1) * 9 + s[0] - '0' - 1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
void selectionSort(int*,int);
int main(){
	int a,b,i,j;
	int array[100];
	scanf("%d",&a);
	for(i=0;i<a;i++){
		scanf("%d",&array[i]);
	}
	selectionSort(array,a);
	return 0;
}

void selectionSort(int* x,int y){
	int i,j,count=0,flag;
	int minj;
	int change;
	for(i=0;i<=y-1;i++){
		minj=i;
		flag=0;
		for(j=i;j<=y-1;j++){
			if(x[j]<x[minj]){
				minj=j;
				flag=1;
			}
		}
		if(flag==1){
			count++;
		}
		change=x[i];
		x[i]=x[minj];
		x[minj]=change;
	}
	for(i=0;i<y;i++){
		if(i==y-1){
			printf("%d\n",x[i]);
		}
		else{
			printf("%d ",x[i]);
		}
	}
	printf("%d\n",count);
}


Measured memory_bytes: 2144
#include <stdio.h>
int main() {
  int x, y, n;
  while (1) {
    scanf("%d %d", &x, &y);
    if (x == 0 && y == 0) {
      break;
    }
    else if (x > y) {
      n = x;
      x = y;
      y = n;
    }
    printf("%d %d\n", x, y);
  }
  return 0;
}

Measured memory_bytes: 1696
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  string ans = "Yes";
  for (int i=0; i<s.size(); i++){
    if(i%2==1 && s[i]=='R') ans="No";
    if(i%2==0 && s[i]=='L') ans="No";
  }
  cout << ans << endl;
}
      

Measured memory_bytes: 256
N,X = map(int,input().split())
W = list(map(int,input().split())) + [X]
W = sorted(W)
dist = 10**18
if len(W) == 2:
  print(W[1]-W[0])
  exit()
for i in range(1,N+1):
  dist = min(dist, W[i]-W[i-1])
  while (W[i]-W[i-1])%dist != 0:
    dist -= 1
  if dist == 1:
    break
print(dist)

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

int main(){
	int data_set;
	std::cin >> data_set;
	std::cin.get();
	std::string document[data_set];
	for(int i = 0; i < data_set; ++i){
		std::getline(std::cin, document[i]);
	}
	for(int i = 0; i < data_set; ++i){
		auto pos = document[i].find("Hoshino");
		while(pos != std::string::npos){
			document[i].replace(pos, 7, "Hoshina");
			pos = document[i].find("Hoshino", pos + 7);
		}
		std::cout << document[i] << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1216
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int arr[3005][3005];
int cache[3005][3005][5];
int r,c,k;

int dp(int i,int j,int tk)
{
    if(i>=r || j>=c)
        return -1e18;
    if(i==r-1 && j==c-1)
    {
        if(tk>=3)
            return 0;
        return arr[i][j];
    }
    int &ans=cache[i][j][tk];
    if(ans!=-1)
        return ans;
    ans=max(dp(i+1,j,0),dp(i,j+1,tk));
    if(tk!=3)
        ans=max({ans,arr[i][j]+dp(i+1,j,0),arr[i][j]+dp(i,j+1,tk+1)});
    //print(i,j,tk,ans);
    return ans;
}
int32_t main() 
{
    IOS;
    cin>>r>>c>>k;
    for(int i=0;i<k;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        arr[a-1][b-1]=c;
    }
    memset(cache,-1,sizeof(cache));
    print(dp(0,0,0));
}

Measured memory_bytes: 427240
macro_rules! input {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    let stdin = std::io::stdin();
    let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
    let mut next = move || -> String{
        bytes
            .by_ref()
            .map(|r|r.unwrap() as char)
            .skip_while(|c|c.is_whitespace())
            .take_while(|c|!c.is_whitespace())
            .collect()
    };
    input! {next,
        n: usize,
        a: [usize1; n-1],
    }
    let mut subs = vec![0; n];
    for boss in a {
        subs[boss] += 1;
    }
    for s in subs {
        print!("{}\n", s);
    }
}


Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll mod = 1e9 + 7;
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> cnt(3, 0);
    ll ans = 1;
    rep(i, n) {
        ll pat = 0;
        rep(j, 3) {
            if (cnt[j] == a[i]) {
                if (pat == 0) cnt[j]++;
                pat++;
            }
        }
        ans = (ans * pat) % mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
char str[200005];
int main()
{
    int n, w= 0, r= 0;
    scanf("%d %s", &n, str);
    for(int i=0; i<n; i++)w+= (str[i]=='W'), r+= (str[i]=='R');
    int res= min(w, r);
    w= 0;
    for(int i=0; i<n; i++)
    {
        w+= (str[i]=='W');
        r-= (str[i]=='R');
        res= min(res, w+max(0, r-w));
    }
    printf("%d\n", res);
    return 0;
}


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

int main() {
	int a[3];
	for (int i = 0; i < 3; i++)
		cin >> a[i];
	sort(a, a + 3);
	int res = 0;
	res += a[2] - a[1];
	if (a[0] % 2 != a[1] % 2) {
		a[1]++;
		res++;
	}
	res += (a[1] - a[0]) / 2;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int N;  cin >> N;
vector<double> v(N);
for (int i = 0; i < N; i++) {
    cin >> v[i];
}
sort(v.begin(), v.end());

double ans = 0;
ans = v[0];
for (int i = 1; i < N; i++) {
    ans = (ans + v[i]) / 2;
}

cout << ans << endl;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

//幾何学テンプレート

#define equals(a,b) (fabs((a)-(b))<EPS)

//点
class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0):x(x), y(y){};

  Point operator + (Point p) {return Point (x+p.x, y+p.y);}
  Point operator - (Point p) {return Point (x-p.x, y-p.y);}
  Point operator * (double a) {return Point(a*x, a*y);}
  Point operator / (double a) {return Point(x/a,y/a);}

  double abs(){return (norm());}
  double norm(){return x*x+y*y;}

  bool operator < (const Point &p)const{
    return x!=p.x ? x<p.x:y<p.y;
  }
  bool operator > (const Point &p)const{
    return x!=p.x ? x>p.x:y>p.y;
  }
  bool operator == (const Point &p)const{
    return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
  }
};

//ベクトル
typedef Point Vector;

//内積
double dot(Vector a,Vector b){
  return a.x*b.x+a.y*b.y;
}

//外積
double cross(Vector a,Vector b){
  return a.x*b.y-a.y*b.x;
}

//線分
struct Segment{Point p1,p2;};

//直線
typedef Segment Line;

//円
class Circle{
public:
  Point c;   //中心
  double r;  //半径
  Circle(Point c=Point(),double r=0.0):c(c),r(r){}};

//多角形
typedef vector<Point> Polygon;


static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;

int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>EPS)   return COUNTER_CLOCKWISE;
  if(cross(a,b)<-EPS)  return CLOCKWISE;
  if(dot(a,b)<-EPS)    return ONLINE_BACK;
  if(a.norm()<b.norm())return ONLINE_FRONT;

  return ON_SEGMENT;
}


signed main(){
  double x0,y0,x1,y1;cin>>x0>>y0>>x1>>y1;
  Point p0={x0,y0},p1={x1,y1};
  int q;cin>>q;

  queue<int>que;
  for(int i=0;i<q;i++){
    double x,y;cin>>x>>y;
    Point p2={x,y};
    int temp=ccw(p0,p1,p2);
    que.push(temp);
  }

  while(!que.empty()){
    int temp=que.front();
    if(temp==1){
      cout<<"COUNTER_CLOCKWISE"<<endl;
    }
    if(temp==-1){
      cout<<"CLOCKWISE"<<endl;
    }
    if(temp==2){
      cout<<"ONLINE_BACK"<<endl;
    }
    if(temp==-2){
      cout<<"ONLINE_FRONT"<<endl;
    }
    if(temp==0){
      cout<<"ON_SEGMENT"<<endl;
    }
    que.pop();
  }
  return 0;
}



Measured memory_bytes: 3304
#include <iostream>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,k;
ll t[N];
int check(ll p)
{
    int i=0;
    for(int j=0;j<k;j++)
    {
        ll s=0;
        while(s+t[i]<=p)
        {
            s+=t[i];
            i++;
            if(i==n)
                return n;
        }
    }
    return i;
}
ll solve()
{
    ll left=0;
    ll right=100000*10000;
    ll mid;
    while(right-left>1)
    {
        mid=(right+left)/2;
        int v=check(mid);
        if(v>=n) right =mid;
        else left=mid;
    }
    return right;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>t[i];
    ll ans=solve();
    cout<<ans<<endl;
}

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

using namespace std;

int main()
{
  int c[3][3];
  rep(i, 3){
    rep(j, 3){
      cin >> c[i][j];
    }
  }

  rep(i, 2){
    int C[3];
    rep(j, 3){
      C[j] = c[i][j] - c[i + 1][j];
    }
    if (!(C[0] == C[1] && C[1] == C[2] && C[2] == C[0]))
    {
      cout << "No" << endl;
      return 0;
    }
  }

  rep(i, 2){
    int C[3];
    rep(j, 3){
      C[j] = c[j][i] - c[j][i + 1];
    }
    if (!(C[0] == C[1] && C[1] == C[2] && C[2] == C[0]))
    {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

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



string make_answer(string S, string T, int findpos)
{
	int slen = S.length();
	int tlen = T.length();
	string ans = S;
	for (int pos = 0; pos < findpos; pos++) {
		if (S.at(pos)=='?') ans.at(pos) = 'a';
	}
	for (int tpos = 0; tpos < tlen; tpos++) {
		ans.at(findpos+tpos) = T.at(tpos);
	}
	for (int pos = findpos+tlen; pos < slen; pos++) {
		if (S.at(pos)=='?') ans.at(pos) = 'a';
	}
	return ans;
}


int main(void) {
	string S, T;
	cin >> S >> T;

	vector <string> answers;
	int tlen = T.length();
	int slen = S.length();
	for (int spos = 0; spos <=(slen-tlen); spos++) {
		bool found = true;
		for (int tpos = 0; tpos < tlen; tpos++) {
			if ((S.at(spos+tpos) != T.at(tpos)) && (S.at(spos+tpos) != '?')) {
				found = false;
				break;
			}
		}
		if (found) {
			string ans = make_answer(S, T, spos);
			answers.push_back(ans);
		}
	}

	std::sort(answers.begin(), answers.end());
	if (answers.size() > 0) {
		cout << answers.at(0) << endl;
	} else {
		cout << "UNRESTORABLE" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
using namespace std;
#define ll long long
#define mod 1000000007;


int main() {
	int n, b[110], a[110], ans = 0;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> b[i];
	}
	a[n - 1] = b[n - 2];
	for (int i = n - 1; i > 0; i--) {
		a[i] = min(b[i], b[i - 1]);
	}
	a[0] = b[0];
	a[n - 1] = b[n - 2];
	for (int i = 0; i < n; i++) {
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    int n;
    cin >> n;
    int ac = 0, tle = 0, re = 0, wa = 0;
    string s;
    while (n--)
    {
        cin >> s;
        if (s == "AC")
            ac++;
        else if (s == "RE")
            re++;
        else if (s == "WA")
            wa++;
        else
            tle++;
    }
    cout << "AC x " + to_string(ac) << endl;
    cout << "WA x " + to_string(wa) << endl;
    cout << "TLE x " + to_string(tle) << endl;
    cout << "RE x " + to_string(re) << endl;
}

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

int main(){
  string T;
  string answer = "";
  cin >> T;

  for(int i=0; i<T.size(); i++){
    if(T.at(i)=='P'){answer.push_back('P');}
    else if(T.at(i)=='D'){answer.push_back('D');}
    else if(T.at(i)=='?'){answer.push_back('D');}
  }
  cout << answer << endl;
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
 
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double PI = 4*atan(1);
typedef long long ll;
typedef pair<int,int> pii;
// int gcd(int a, int b) { 
//     if (a == 0) return b; 
//     return gcd(b % a, a); 
// }
// ll power(int base, int power) {
// 	ll prod = 1;
// 	ll b = base;
// 	while(power) {
// 		if (power & 1) {
// 			prod = f(prod*b);
// 		}
// 		b = f(b*b);
// 		power/=2;
// 	}
// 	return prod;
// }
// struct line {
//     int m, c;
//     ll eval(int x) { return 1LL * m * x + c; }
//     double intersectX(line l) { return (double) (c - l.c) / (l.m - m); }
// };
int S,W;
void solve() {
	cin >> S >> W;
	if (S>W) {
		cout << "safe\n";
	} else {
		cout << "unsafe\n";
	}

}
int main() {
	int t;
	// cin >> t;
	// for (int i = 1; i <= t; i++) { 
		// cout << "Case #" << i << ": ";
		solve();
	// }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, ans;
char s[MAXN]; 
signed main() {
	scanf("%s", s + 1);
	N = strlen(s + 1);
	LL sum = 0, ans = 0;
	for(int i = 1; i <= N; i++) {
		if(s[i] == 'W') ans += sum;
		if(s[i] == 'B') sum++; 
	}
	cout << ans;
    return 0;
}

Measured memory_bytes: 384
const main = (input) => {
  const inputs = input.split('\n');
  const H = Number.parseInt(inputs[0].split(" ")[0]);
  const W = Number.parseInt(inputs[0].split(" ")[1]);
  const h = Number.parseInt(inputs[1].split(" ")[0]);
  const w = Number.parseInt(inputs[1].split(" ")[1]);

  console.log(H*W-w*H-h*W+h*w);


}

main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));


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

int main() {
  int n;
  cin >> n;
  int d[n];

  for(int i = 0; i < n; i++){
      cin >> d[i];
  }
  int dan = 1;

  sort(d, d + n);
  for(int i = 0; i < n - 1; i++){
      if(d[i] < d[i + 1]){
          dan += 1;
      }
  }
    cout << dan << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int wide = Integer.parseInt(sc.next());
        int height = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int h = Integer.parseInt(sc.next());
        BigDecimal wi = BigDecimal.valueOf(wide);
        BigDecimal he = BigDecimal.valueOf(height);
        BigDecimal two = BigDecimal.valueOf(2);
        BigDecimal res = wi.multiply(he);
        res = res.divide(two);
        int i = 0;
        if(wide%2==0&&w*2==wide) {
            if(height%2==0&&h*2==height) {
                i = 1;
            }
        }
        System.out.println(res+" "+i);
    }
}


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

int main()
{
  string s;cin >>s;
  sort(s.begin(),s.end());
 if(s.at(1)==s.at(0)&& s.at(3)==s.at(2)&& s.at(2)!=s.at(1))
   cout <<"Yes";
   else
     cout <<"No";
}






Measured memory_bytes: 256