akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define YES cout<<"YES"<<endl
#define all(v) v.begin(),v.end()
#define NO cout<<"NO"<<endl
#define pb(x) emplace_back(x)
#define fastio std::ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define vi vector<ll>
#define mi map<ll,ll>
#define pi pair<ll,ll>
#define what(x) cout<<#x<<" ="<<x<<endl;
using namespace std;
using ll =long long;

ll dp[1005][1005];
string a[1000+5];
ll mod=1e9+7,n,m;
ll solve(ll i,ll j)
{
    if(i==n-1 && j==m-1)return 1;
    if(i>=n ||i<0 || j>=m || j<0) return 0;
    if(dp[i][j]!=-1)return dp[i][j]%mod;
    dp[i][j]=0;
    if(i+1<n)if(a[i+1][j]!='#')dp[i][j]=(solve(i+1,j))%mod;
    if(j+1<m)if(a[i][j+1]!='#')dp[i][j]=(dp[i][j]%mod+solve(i,j+1)%mod)%mod;

    return dp[i][j]%mod;

}



int main()
{

    memset(dp,-1,sizeof dp);
    cin>>n>>m;



    fr(i,0,n)cin>>a[i];

    cout<<solve(0,0)<<endl;










}




























Measured memory_bytes: 13480
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>

using namespace std;

double dis(long double x1,long double y1,long double x2,long double y2);

int main(){
	long double x1,y1,r1;
	long double x2,y2,r2;
	long double ans;
	double r[2];
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x1>>y1>>r1;
		cin>>x2>>y2>>r2;
		
		ans=dis(x1,y1,x2,y2);
		
		if(ans>r1+r2){
			cout<<"0"<<endl;
		}else if(ans<=r1+r2){
				if(r2>ans+r1){
					cout<<"-2"<<endl;
					continue;
				}else if(r1>ans+r2){
					cout<<"2"<<endl;
					continue;
				}
			
			cout<<"1"<<endl;
		}
	
	}
}

double dis(long double x1,long double y1,long double x2,long double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

Measured memory_bytes: 1228
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] p = new int[n];
        for(int i = 0; i < n; i++){
            p[i] = scan.nextInt();
        }
        int c = 0;
        for(int i = 0; i < n; i++){
            if(p[i] != i + 1){
                c++;
            }
        }
        if(c == 2 || c == 0){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 21844
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def print_lcs (a, b, lcs, i, j, cur):
    if i==0 or j==0:
        return cur
    
    elif a[i] == b[j]:
        ans = print_lcs(a,b,lcs,i-1,j-1,cur+a[i])
        return ans
    
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            return print_lcs(a,b,lcs,i-1,j,cur)
        else:
            return print_lcs(a,b,lcs,i,j-1,cur)
        


s = " " + ns()
t = " " + ns()

lens = len(s)
lent = len(t)

lcs = [[0]*lent for _ in range(lens)]
ans = ""
for i in range(1,lens):
    for j in range(1,lent):
        if s[i] == t[j]:
            lcs[i][j] = lcs[i-1][j-1] + 1

            
        else:
            if lcs[i-1][j] > lcs[i][j-1]:
                lcs[i][j] = lcs[i-1][j]
            else:
                lcs[i][j] = lcs[i][j-1]
                
print(print_lcs(s,t,lcs,lens-1,lent-1,"")[::-1])

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

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pll = pair<ll, ll>;

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

template <class T1, class T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T1, class T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;
constexpr ll mod = 1000000007;

int main() {
    ll N, K, C;
    cin >> N >> K >> C;
    string S;
    cin >> S;

    vector<ll> forward(K);
    vector<ll> reverse(K);

    ll cnt = 0;
    for (ll i = 0; i < N; ++i) {
        if (S[i] == 'o') {
            forward[cnt] = i;
            ++cnt;

            if (cnt == K) break;

            i += C;
        }
    }

    cnt = K - 1;
    for (ll i = N - 1; i >= 0; --i) {
        if (S[i] == 'o') {
            reverse[cnt] = i;
            --cnt;

            if (cnt == -1) break;
            i -= C;
        }
    }

    for (ll i = 0; i < K; ++i) {
        if (forward[i] == reverse[i]) {
            cout << forward[i] + 1 << endl;
        }
    }
}

Measured memory_bytes: 6564
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 111111
int n;
double pw,vw[N],pf[N],vf[N],th[N],ans;
double calc(double x){
  double res=pw*x;
  for(int i=0;i<n;i++) res+=max(0.0,(th[i]-vw[i]*x)*pf[i]/vf[i]);
  ans=min(ans,res);
  return res;
}
int main(){
  while(cin>>n,n){
    cin>>pw;
    for(int i=0;i<n;i++) scanf("%lf%lf%lf%lf",vw+i,pf+i,vf+i,th+i);
    double l=0,r=1e9;
    ans=calc(0);
    for(int i=0;i<100;i++){
      double m1=l+(r-l)/3,m2=l+(r-l)*2/3;
      if(calc(m1)>calc(m2)) l=m1;
      else r=m2;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 6460
n = int(input())
s = input()
mod = 10**9 + 7

cnt = [0] * 26
for i in range(26):
    cnt[i] = s.count(chr(i+97)) + 1

ans = 1
for i in cnt:
    ans *= i
    ans %= mod

ans -= 1
ans %= mod
print(ans)

Measured memory_bytes: 39024
N,*uvws=$<.read.split.map(&:to_i)

h = {}
uvws.each_slice(3) do |u,v,w|
    h[u] ||= []
    h[u] << [u,v,w%2]
    h[v] ||= []
    h[v] << [v,u,w%2]
end

arr = Array.new(N+1,-1)
arr[1] = 0

q = h[1]
until q.empty?
    u,v,w = q.shift
    next if arr[v] != -1
    if w == 0
        arr[v] = arr[u]
    else
        arr[v] = 1-arr[u]
    end
    h[v].each do |x|
        q << x
    end
end

puts arr[1..-1]

Measured memory_bytes: 55124
a, b, c, x, y = map(int, input().split())

if a + b < 2 * c:
    ans = a * x + b * y
    print(ans)
else:
    if x < y:
        ans = (y - x) * b + c * 2 * x
        print(ans if ans < 2 * c * y else 2 * c * y)
    else:
        ans = (x - y) * a + c * 2 * y
        print(ans if ans < 2 * c * x else 2 * c * x)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int count = 0;
			int s = (int) Math.sqrt((double) n);
			for (int i = 1; i <= s; i++) {
				if (n % i == 0) {
					count += i;
					count += (n / i);
					if (n / i == 1)
						count -= (n / i);
					if (n / i == i)
						count -= (n / i);
					if (n / i == n)
						count -= n;
				}
			}
			if (n > count)
				System.out.println("deficient number");
			else if (n == count)
				System.out.println("perfect number");
			else
				System.out.println("abundant number");
		}

	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<cstdio>
using namespace std;
#define NIL -1
struct Node
{
    int parent,left,right;
}T[100005];
int n,D[100005]; //用来储存深度
void print(int u)
{
    cout<<"node "<<u<<": ";
    cout<<"parent = "<<T[u].parent<<", ";
    cout<<"depth = "<<D[u]<<", ";

    if(T[u].parent==NIL) cout<<"root, ";
    else if(T[u].left==NIL) cout<<"leaf, ";
    else cout<<"internal node, ";
    cout<<"[";

    for(int i=0,c=T[u].left ;c!=NIL; i++,c=T[c].right) //求子节点
    {
        if(i) cout<<", ";
        cout<<c;
    }

    cout<<"]"<<endl;
}
int rec(int u,int p) //求深度(递归)
{
    D[u]=p;
    if(T[u].right!=NIL) rec(T[u].right,p); //求出所有同一深度节点的深度
    if(T[u].left!=NIL) rec(T[u].left,p+1); //求出下方节点的深度
}
int main()
{
    //freopen("number.txt","r",stdin);
    int v,d,c,r,l;
    cin>>n;
    for(int i=0;i<n;i++) T[i].parent=T[i].left=T[i].right=NIL; //初始化
    for(int i=0;i<n;i++)
    {
        cin>>v>>d;
        for(int j=0;j<d;j++)
        {
            cin>>c;
            if(j==0)
            {
                T[v].left=c;
                l=T[v].left;
            }
            else T[l].right=c;
            l=c; //更新l的位置，l是最右边的节点
            T[c].parent=v;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(T[i].parent==NIL) r=i;
    }
    rec(r,0);
    for(int i=0;i<n;i++) print(i);
    return 0;
}


Measured memory_bytes: 7704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000000;

int main()
{
    int n,a;
    double z=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a);
        z+=(1.0/a);
    }
    printf("%.6f",1.0/z);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace	std;
int main(){

  int n,a[45],i;

  cin>>n;
  a[0]=1;
  a[1]=1;

  for(i=2;i<=n;i++) a[i]=a[i-2]+a[i-1];

  cout<<a[n]<<endl;

  return 0;

}

Measured memory_bytes: 3084
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#define db double
#define ui unsigned int
#define ll long long
#define ull unsiged ll
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l)for(int i=r;i>=l;i--)
#define boots ios::sync_with_stdio(0); cin.tie(0)
#define pb push_back
#define pp pop_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define vii vector<int>
#define vll vector<ll>
#define vpp vector<pii>
#define inf  0x3f3f3f3f
#define lnf LLONG_MAX
#define mii map<int,int>
#define mll map<ll,ll>
#define mil map<int,ll>
#define umii unordered_map<char,int>
#define umll unordered_map<ll,ll>
#define umcc unordered_map<char,char>
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pf(n) printf("%lld\n",n)
#define sz size()
using namespace std;
const db pi = 3.1415926535898;
const int MX = 1e3 + 7;
const int esp = 1e-6;
ll INV2, INV6;
ll modulo(ll num, ll MOD = mod) { return ((num%MOD) + MOD) % MOD; }
ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a%b)); }
unordered_map<ui, ll>mp1, mp;
int p[MX][MX];
int sum[MX][MX];
char s[MX / 10];
vector<int> pri;
vector<bool> isp(MX, true);
int k;
int ant[MX];
int n;
ll qpow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return ans;
}
ll INV(ll n)
{
	return qpow(n, mod - 2);
}
ll get_sum(ll d)
{
	if (d == 1)return k - 1;
	return d * d%mod*(qpow(d, k )*INV(d) - 1) % mod*INV(d - 1) % mod;
}
ll get_sum2(int n)
{
	return n * (n + 1) % mod*(2 * n + 1) % mod*INV6%mod;
}
bool vj()
{
	rep(i, 1, n)
	{
		if (ant[i] != n)return 0;
	}
	return 1;
}
int main()
{
	boots;
	cin >> n;
	rep(i, 1, n)rep(j, 1, n - 1)cin >> p[i][j];
	int ans = 0;
	rep(i, 1, n)ant[i] = 1;
	bool ji[MX];
	int temp = 0;
	while (true)
	{
		temp = 0;
		memset(ji, 0, sizeof(ji));
		if (vj()) { cout << ans << endl; return 0; }
			ans++;
			int temp = 0;
		rep(i, 1, n)
		{
			if (ant[i] == n || ji[i])continue;
			int u = p[i][ant[i]], v = p[u][ant[u]];
			if (!ji[u] && !ji[i] &&v==i)
			{
				ant[u]++;
				ant[v]++;
				ji[u] = ji[v] = 1;
				temp++;
			}
			//cout << ans << endl;
		}
			if (!temp) { cout << "-1" << endl; return 0; }
	}
}

Measured memory_bytes: 6144
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

fun main(args: Array<String>) {
    val (a, b, c) = readInts()
    val sum = a + b + c
    println(if (setOf(a + b, b + c, a + c).contains(sum / 2)) "Yes" else "No")
}

Measured memory_bytes: 38048
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (int i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (int i = x.size()-1; i >= 0; i--)
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define fst first
#define scd second
#define nextline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

ll ans, n, k;
map<ll, ll> h;

int main()
{
    cin>>n>>k;
    REP(i,n) {
        ll tmp;
        cin>>tmp;
        h[tmp]++;
    }
    while (k) {
        auto itr = h.end();
        if (itr == h.begin()) {
            break;
        }
        itr--;
        if (k >= itr->second) {
            k -= itr->second;
            //ans += itr->second;
            h.erase(itr);
        } else {
            itr->second -= k;
            //ans += k;
            k = 0;
        }
    }
    for(auto itr = h.begin(); itr != h.end(); itr++) {
        ans += itr->first * itr->second;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define rep(i, s, n) for(int i = s; i < n; i++)

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, 0, h) cin >> s[i];
    int x[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    int y[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    vector<vector<int>> ans(h);
    rep(i, 0, h) {
        rep(j, 0, w) {
            int val = 0;
            rep(k, 0, 8) {
                int px = i+y[k];
                int py = j+x[k];
                if(px >= 0 && px < h && py >= 0 && py < w) {
                    if(s[px][py] == '#') val++;
                }
            }
            if(s[i][j] == '.') cout << val;
            else cout << '#';
            //ans[i][j] = val;
            //cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

#define INPUT_FROM_FILE (0) 
#if INPUT_FROM_FILE
#include <fstream>
#endif

typedef std::pair<int, int> P; //first:最短距離，second:頂点番号

class Edge{
public:
	int to;
	int cost;

	Edge(){
		return;
	}
	~Edge(){
		return;
	}
};

#define MAX_COST (1000000000)

int main(int argc, char **argv){
	int n, m, r;
	std::vector<std::vector<Edge> > G;
	std::vector<long> min_cost;
	std::priority_queue<P, std::vector<P>, std::greater<P> > que;

#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
	//FILE *fp = fopen("test.txt", "r");
#endif
	
	
#if INPUT_FROM_FILE
	ifs >> n >> m >> r;
#else
	std::cin >> n >> m >> r;
#endif
	G.resize(n);

	for(int i = 0; i < m; i++){
		int s, t, d;
		Edge edge;

#if INPUT_FROM_FILE
		ifs >> s >> t >> d;
#else
		std::cin >> s >> t >> d;
#endif

		edge.to = t;
		edge.cost = d;
		G[s].push_back(edge);
	}

	min_cost.resize(n, MAX_COST);
	min_cost[r] = 0;
	que.push(P(0, r));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(min_cost[v] < p.first) continue;
		
		for(int i = 0; i < G[v].size(); i++){
			Edge &e = G[v][i];

			if(min_cost[e.to] > min_cost[v] + e.cost){
				min_cost[e.to] = min_cost[v] + e.cost;
				que.push(P(min_cost[e.to], e.to));
			}
		}
	}

	for(int i = 0; i < n; i++){
		if(min_cost[i] == MAX_COST){
			std::cout << "INF" << std::endl;
		}
		else{
			std::cout << min_cost[i] << std::endl;
		}
	}
	return 0;
}


Measured memory_bytes: 13280
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	string s;
	cin >> s;
	for(auto c: s){
		if(c == '7'){
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main(){
  int N,K;
  cin >>N>>K;
  map<int,int> A;
  for(int i=0;i<N;i++){
    int temp;
    cin >> temp;
    A[temp]++;
  }
  vector<int> v;
  for(auto it=A.begin();it!=A.end();it++){
    v.push_back(it->second);
  }
  sort(v.begin(),v.end());
  int ans=0;
  int num=v.size();
  int i=0;
  while(num>K){
    ans+=v[i];
    num--;
    i++;
  }

  cout << ans <<endl;

  return 0;
}


Measured memory_bytes: 10748
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int A,B,sum;
    scanf("%d %d",&A,&B);
    if(A==B)
        sum=A+B;
    else if(A>B)
        sum=A+A-1;
    else
        sum=B+B-1;
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n, k; cin >> n >> k;
    vector<ll> h(n+1, 0);
    repr(i, 1, n+1) cin >> h[i];

    const ll inf = 1LL<<60;
    vector<vector<ll>> dp(n+5, vector<ll>(n+5, inf));
    dp[0][0] = 0;
    
    repr(x, 1, n+1) repr(y, 1, x+1){
        rep(i, x) chmin(dp[x][y], dp[i][y-1]+max(0LL, h[x]-h[i]));
    }
    ll ans = inf;
    repr(i, n-k, n+1) chmin(ans, dp[i][n-k]);
    cout << ans << endl;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline

N = int(input())
P = list(map(int,input().split()))
P = [p-1 for p in P]

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
      l, r = l >> 1, r >> 1
      
STA = SegmentTree(N,0)
STB = SegmentTree(N,0)

STA.build(list(range(N)))
STB.build(list(range(N)[::-1]))

prev = P[0]
for p in P[1:]:
  toadd = (STA.get(prev)+STB.get(prev)) - (STA.get(p)+STB.get(p)) + 1
  toadd = max(0,toadd)
  if p>prev:
    STA.add(p,N,toadd)
    if p+1 <= N-1:
      STB.add(p+1,N,-toadd)
  else:
    STB.add(0,p+1,toadd)
    if p >= 1:
      STA.add(0,p,-toadd)
  prev = p
  
ansa = [STA.get(i) for i in range(N)]
ansb = [STB.get(i) for i in range(N)]

mina = min(ansa)
minb = min(ansb)

ansa = [i-mina+1 for i in ansa]
ansb = [i-minb+1 for i in ansb]

print(*ansa)
print(*ansb)


Measured memory_bytes: 73952
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long MOD = 1000000007;

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

	int h, n;
	cin >> h >> n;
	rep(i, n) {
		int a;
		cin >> a;
		h -= a;
	}

	if (h <= 0) cout << "Yes" << "\n";
	else cout << "No" << "\n";

	return 0;
}


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

int main() {
    int n, y; scanf("%d%d", &n, &y);
    int y10000=-1, y5000=-1, y1000=-1;

    int t;
    for (int i = 0; i<= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            t = (y - 10000*i - 5000*j)/1000;
            if (t==n-i-j) {y10000=i; y5000=j; y1000=t;}
            if (y1000>0) break;
        }
        if (y1000>0) break;
    }

    printf("%d %d %d\n", y10000, y5000, y1000);
    return 0;
}

Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll k=1<<9,mx=100005;
int main(){
    ll n,q;cin>>n;
    chmin(k,n);
    vi v(n),w(n);
    rep(i,n)cin>>v[i]>>w[i];
    cin>>q;
    vvi memo(k,vi(mx));
    rep(i,k){
        chmax(memo[i][w[i]],v[i]);
        if(i){
            ll p=(i-1)/2;
            rep(j,mx-w[i])chmax(memo[i][w[i]+j],memo[p][j]+v[i]);
            rep(j,mx)chmax(memo[i][j],memo[p][j]);
        }
        REP(j,1,mx)chmax(memo[i][j],memo[i][j-1]);
    }
    rep(qq,q){
        ll x,y;cin>>x>>y;
        x--;
        vi t;
        while(x>=k){
            t.pb(x);x=(x-1)/2;
        }
        ll ans=memo[x][y];
        ll s=t.size();
        rep(bit,1<<s){
            ll V=0,W=0;
            rep(i,s)if(bit>>i&1){
                V+=v[t[i]];W+=w[t[i]];if(y-W<0)break;
            }
            if(y-W>=0)chmax(ans,V+memo[x][y-W]);
        }
        out(ans);
    }
}

Measured memory_bytes: 409536
N = gets.chomp.to_i

ans = 0

ab_cnt = 0
tail_a_cnt = 0
head_b_cnt = 0

N.times do |i|
  s = gets.chomp

  ans += s.scan('AB').length

  if s[0] == 'B' && s[-1] == 'A'
    ab_cnt += 1
  elsif s[0] == 'B'
    head_b_cnt += 1
  elsif s[-1] == 'A'
    tail_a_cnt += 1
  end
end

# abは足してもabなので残り1つになるまで答えにたす
# p ab_cnt
# p tail_a_cnt
# p head_b_cnt

if ab_cnt > 0
  # 残り1つになるまで足す
  ans += ab_cnt-1

  # aかbがあればそれに置き換えられるので足す
  ans += 1 if tail_a_cnt > 0 || head_b_cnt > 0
end

ans += [head_b_cnt,tail_a_cnt].min

p ans


Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  set<int> st;
  for(int i=0;i<k;i++)
  {
    int s;
    cin>>s;
    for(int i=0;i<s;i++)
    {
      int a;
      cin>>a;
      st.insert(a);
    }
  }
  cout<<n-st.size();
  return 0;
}  

Measured memory_bytes: 3616
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N; cin>>N;    ll L=sqrt(N) +2;
    vector<ll> ans(N+1,0);
    rep1(x,L)rep1(y,L)rep1(z,L){
        ll tmp = x*x + y*y + z*z + x*y + y*z + z*x;
        if(tmp <= N) ans[tmp]++;
    }
    rep1(i,N) cout<<ans[i]<<endl;
}



Measured memory_bytes: 3616
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
	char c=nc();int len=1;
	for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
	for(;(c>='a' && c<='z');s[len++]=c,c=nc());
	s[len++]='\0';
	return len;
}

inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}

int wt,ss[19];
inline void print(int x){
	if (x<0) x=-x,putchar('-'); 
	if (!x) putchar(48); else {
	for (wt=0;x;ss[++wt]=x%10,x/=10);
	for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
	if (x<0) x=-x,putchar('-');
	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,a[200010];

bool check1(int x)
{
	for (int i=1;i<2*n;i+=2)
		if (a[i]<x) return false;
	return true;
}

bool check(int x)
{
	if (check1(x)) return true;
	int y=0,z;
	for (int i=1;i<n;i++)
		if (a[i]>=x && a[i+1]>=x) y=i+1;
	z=y;
	if (z!=0)
	{
		while (a[z+2]>=x)
		{
			z+=2,y++;
			if (z+2>=2*n) break;
		}
		if (y>=n) return true;
	}
	y=0;
	for (int i=2*n-1;i>n;i--)
		if (a[i]>=x && a[i-1]>=x) y=i-1;
	z=y;
	if (z!=0)
	{
		while (a[z-2]>=x)
		{
			z-=2,y--;
			if (z-2<1) break;
		}
		if (y<=n) return true;
	}
	return false;
}

int main()
{
	read(n);
	memset(a,0,sizeof(a));
	for (int i=1;i<2*n;i++)
		read(a[i]);
	int l=2,r=2*n-2,mid,res;
	while (l<=r)
	{
		mid=l+r>>1;
		if (check(mid)) l=mid+1,res=mid;else r=mid-1;
	}
	print(res),puts("");
	return 0;
}


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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000000
//3
typedef long long ll;
typedef pair<int,int> pii;
priority_queue< int > pq;
priority_queue< int , vector<int> , greater<int> > rpq;
set<int>s;
set <int > :: iterator itr; 
vector<int> vec[1001];
int r,n,m,inp,tc;
int arr[1000007]= {};
map<int , int> mymap;


int main()
{
	int n;
	cin>>n;
	for(int i=1 ; i<=n ; i++){
		scanf("%d",&arr[i]);
	}
	arr[0] = arr[1];
	int dp[100007]= {0};
	dp[0] = 0;
	dp[1] = 0;
	for(int i=2; i<= n ; i++){
			int x = dp[i-1] + (abs(arr[i] - arr[i-1]));
			//cout<<dp[i-1]<<" "<<arr[i]<<" "<<arr[i-1]<<endl;
			int y = dp[i-2] + (abs(arr[i] - arr[i-2]));
			//cout<<dp[i-2]<<" "<<arr[i]<<" "<<arr[i-2]<<endl;
			//cout<<x<<" "<<y<<endl;
			dp[i] = min( x,y );
	}
	
//	for(int i=0 ;i <=n ; i++)
//	cout<<dp[i]<<" ";
//	cout<<endl;
	cout<<dp[n]<<endl;
    return 0;
}

//65 900 17 13

Measured memory_bytes: 1024
a[20],z=1e4,n;*p;main(m){for(;scanf("%d%d",&m,&n)*n;puts(a))for(*a=1;~n--;)for(p=a+18;p-->a;)*p=~n?p[1]+=*p*m/10000,*p*m%10000:*p&&!printf("%d%.3s",*p,"MtsFksNytAsgGgsGokSaiSeiKanKo\0JouJo\0GaiKeiChoOkuMan"+(a-p+17)*3);}

Measured memory_bytes: 616
#include <stdio.h>

main(){
    int N,M;
    scanf("%d %d",&N,&M);
    int flag[50][6]={{0,},};
    int i,j,k;
    char c;
    int nuru,minnuru;
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            switch(getchar()){
                case 'W':
                    flag[i][0]++;
                    break;
                case 'B':
                    flag[i][1]++;
                    break;
                case 'R':
                    flag[i][2]++;
                    break;
                default :
                    j--;
                    continue;
            }
        }
        for(j=3;j<6;j++)
            flag[i][j]=M-flag[i][j-3];
    }
    minnuru=50*50;
    for(i=0;i<N-2;i++){
        for(j=i+1;j<N-1;j++){
            nuru=0;
            for(k=0;k<=i;k++)
                nuru+=flag[k][3];
            for(k=i+1;k<=j;k++)
                nuru+=flag[k][4];
            for(k=j+1;k<=N-1;k++)
                nuru+=flag[k][5];
            if(minnuru>nuru)
                minnuru=nuru;
        }
    }
    printf("%d\n",minnuru);

    return 0;
}

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

typedef long long int lli;

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
int n, m;
lli x[N];
lli y[N];

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

	lli sumX = 0;
	for(int i = 0; i < n; i++) {
		cin >> x[i];
	}
	sort(x, x+n);
	
	for(lli i = 1; i < n; i++) {
		sumX += i*(n-i)*(x[i]-x[i-1]);
		sumX %= MOD;
	}

	lli sumY = 0;
	for(int i = 0; i < m; i++) {
		cin >> y[i];
	}
	sort(y, y+m);
	
	for(lli i = 1; i < m; i++) {
		sumY += i*(m-i)*(y[i]-y[i-1]);
		sumY %= MOD;
	}

	cout << (sumX*sumY)%MOD << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (int i=0;i<N;i++)
#define loop(i,N,M) for(int i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

//変数
ll N;

//解法
void solve() {

	if (N == 25) {
		cout << "Christmas";
		return;
	}
	if (N == 24) {
		cout << "Christmas Eve";
		return;
	}
	if (N == 23) {
		cout << "Christmas Eve Eve";
		return;
	}
	if (N == 22) {
		cout << "Christmas Eve Eve Eve";
		return;
	}

	return;
}

int main() {
	//入力

	cin >> N;

	solve();
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=400005;

struct {
	ll mn=0x7fffffff,lazy=-1;	
} S[maxn];
int n,q;

void update(int id,int ql,int qr,int v,int l,int r) {
	if (ql==l && qr==r) {
		S[id].lazy=v;
		return;
	}
	if (S[id].lazy!=-1) {
		S[id].mn=S[id].lazy;
		if (l!=r) S[id<<1].lazy=S[id<<1|1].lazy=S[id].lazy;
		S[id].lazy=-1;
	}
	int m=l+r>>1;
	if (qr<=m) update(id<<1,ql,qr,v,l,m);
	else if (ql>m) update(id<<1|1,ql,qr,v,m+1,r);
	else update(id<<1,ql,m,v,l,m), update(id<<1|1,m+1,qr,v,m+1,r);
	int lm=S[id<<1].lazy==-1?S[id<<1].mn:S[id<<1].lazy;
	int rm=S[id<1|1].lazy==-1?S[id<<1|1].mn:S[id<<1|1].lazy;
	S[id].mn=min(lm,rm);
}

int query(int id,int i,int l,int r) {
	if (S[id].lazy!=-1) {
		S[id].mn=S[id].lazy;
		if (l!=r) S[id<<1].lazy=S[id<<1|1].lazy=S[id].lazy;
		S[id].lazy=-1;
	}
	if (l==r) return S[id].mn;
	int m=l+r>>1;
	if (i<=m) return query(id<<1,i,l,m);
	else return query(id<<1|1,i,m+1,r);
}

int main() {
	cin>>n>>q;
	for (int i=0;i<q;i++) {
		bool op; cin>>op;
		if (op) {
			int k; cin>>k;
			cout<<query(1,k,0,n-1)<<'\n';
		}
		else {
			int s,t,x;
			cin>>s>>t>>x;
			update(1,s,t,x,0,n-1);
		}
	}
}



Measured memory_bytes: 7196
h,w=map(int,input().split())
n=int(input())
arr=list(map(int,input().split()))
ans=[[0]*w for _ in range(h)]
hpos=0
wpos=0
apos=0
cnt=0
while 1:
  while cnt<arr[apos]:
    ans[hpos][wpos]=apos+1
    if hpos%2==0:
      wpos+=1
      if wpos==w:
        hpos+=1
        wpos=w-1
    else:
      wpos-=1
      if wpos==-1:
        hpos+=1
        wpos=0
    cnt+=1
  cnt=0
  apos+=1
  if hpos==h:
    break
for i in range(h):
  print(*ans[i])

Measured memory_bytes: 3916
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    aa = LI()
    # +から始めるパターン
    cs = 0
    ans1 = 0
    for i, a in enumerate(aa):
        cs += a
        if i % 2:
            if cs >= 0:
                ans1 += abs(-1 - cs)
                cs = -1
        else:
            if cs <= 0:
                ans1 += abs(1 - cs)
                cs = 1
    # -から始めるパターン
    cs = 0
    ans2 = 0
    for i, a in enumerate(aa):
        cs += a
        if i % 2:
            if cs <= 0:
                ans2 += abs(1 - cs)
                cs = 1
        else:
            if cs >= 0:
                ans2 += abs(-1 - cs)
                cs = -1
    print(min(ans1,ans2))

main()


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int k;
  vector<int> a(3);
  cin >> a[0] >> a[1] >> a[2] >> k;
  sort(a.begin(), a.end());
  int ans = a.back() * pow(2, k) + a[0] + a[1];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int ctoi(char c){
	return c - '0';
}


int main(){
	string s;
	cin >> s;
	if (ctoi(s[s.length()-1]) == 3){
		cout << "bon" << endl;
	}else if (ctoi(s[s.length()-1]) <= 1 || ctoi(s[s.length()-1]) == 6 || ctoi(s[s.length()-1]) == 8){
		cout << "pon" << endl;
	}else{
		cout << "hon" << endl;
	}
	return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	string s; cin>>s;
	int n=s.length();
	if(s[0]=='A'){
		if(count(s.begin(),s.end(),'C')==1){
			int pos=find(s.begin(),s.end(),'C')-s.begin();
			if(2<=pos && pos<n-1){
				bool ok=true;
				rep(i,n) if(i!=0 && i!=pos && isupper(s[i])) ok=false;
				if(ok){
					cout<<"AC"<<endl;
					return 0;
				}
			}
		}
	}
	cout<<"WA"<<endl;

	return 0;
}


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

using namespace std;


int main() {
	int n, a, t;
	cin >> n >> t >> a;
	int H = (int)(((double)(t - a) / 0.006)+0.5);

	int k = -1;
	int s = -100000000;
	for (int i = 0; i < n; i++) {
		int h; cin >> h;
		if (abs(H - h) < abs(H - s)) {
			k = i+1;
			s = h;
		}
	}
	cout << k;

	return 0;
}

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

map<string,int> data;
map<string,map<string,int> >tree;

int cal(string str){
	int r=data[str];
	int sum=-1;
	map<string,int>::iterator itr=tree[str].begin();
	for(;itr!=tree[str].end();itr++){
		
		if(itr->second==1)sum+=cal(itr->first);
		
	}
	if(sum!=-1)return min(sum+1,r);
	else return r; 
}

int main(){
	int n;
	
	while(cin>>n && n){
		tree.clear();
		string str;
		int cost;
		for(int i=0;i<n;i++){
			cin>>str>>cost;
			data[str]=cost;
		}
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			string in;
			int num;
			cin>>in>>num;
			for(int j=0;j<num;j++){
				string tmp;
				cin>>tmp;
				tree[in][tmp]=1;
			}
		}
		
		string ma;
		cin>>ma;
		
		cout<<cal(ma)<<endl;
		
		
	}
	
}

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

int main()
{
  //input
  int N;
  cin >> N;
  int a[N],b[N];
  for(int i=0;i<N;i++){cin >> b[i];}
  
  //main
  for(int i=N-1;i>=0;i--){
    if(i == N-1) a[i] = b[i-1];
    else if(i == 0){a[i] = b[i];}
    else {
      a[i] = min(b[i],b[i-1]);
    }
  }
  
  
  //output
  int ans = 0;
  for(int i=0; i<N; i++){ans += a[i];}
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
x, y = map(int, input().split())
a = (y - 2*x)/2
b = (4*x-y)/2
if a + b == x and 4*a + 2*b == y and a % 1 == 0 and b % 1 == 0 and a>= 0 and b>= 0:
  print("Yes")
else : 
  print("No")

Measured memory_bytes: 9164
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

char S[101010];

bool hoge(int a, int x)
{
	return a == x || a == x + 1;
}

bool test(int a, int b, int c)
{
	int mn = min(a, min(b, c));
	return hoge(a, mn) && hoge(b, mn) && hoge(c, mn);
}

int main()
{
	scanf("%s", S);
	int a = 0, b = 0, c = 0;
	for (int i = 0; S[i]; ++i) {
		if (S[i] == 'a') ++a;
		else if (S[i] == 'b') ++b;
		else ++c;
	}
	puts(test(a, b, c) ? "YES" : "NO");

	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair

ll tree[4*200003],a[200003],h[200003],dp[200003];

void build(int node,int start,int end){
	if(start == end){
		tree[node] = 0;
	}
	else{
		int m = (start+end)/2;
		build(2*node,start,m);
		build(2*node+1,m+1,end);
		tree[node] = max(tree[node*2],tree[node*2+1]);
	}
}

void update(int node,int start,int end,int idx,ll val){
	if(start == end){
		tree[node] = max(val,tree[node]);
	}
	else{
		int m = (start+end)/2;
		if(idx>=start && idx<=m)
		{
			update(2*node,start,m,idx,val);
		}
		else{
			update(2*node+1,m+1,end,idx,val);
		}
		tree[node] = max(tree[node*2],tree[node*2+1]);
	}
}

ll query(int node,int l,int r,int start,int end){
	if(r<start || l>end){
		return 0;
	}
	if(l<=start && r>=end){
		return tree[node];
	}

	int m = (start+end)/2;
	return max(query(2*node,l,r,start,m),query(2*node+1,l,r,m+1,end));

}
int main(){
	int n,i;
	scanf("%d",&n);
	build(1,1,n);
	for(i=1;i<=n;i++){
		scanf("%lld",&h[i]);
	}
	for(i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	dp[0]=0;
	for(i=1;i<=n;i++){
		ll val = a[i] + query(1,1,h[i]-1,1,n);
		update(1,1,n,h[i],val);
		dp[i]= max(dp[i-1],val); 
	}
	ll ans=0;
	for(i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	printf("%lld\n",ans );
	
	return 0;
}

Measured memory_bytes: 10496
def main():
    from collections import deque
    from decimal import Decimal, getcontext

    getcontext().prec = 1000

    N = int(input())

    # {1,...,N}*2を分割
    # k個の集合があって
    # 各集合は他のk-1個の集合に対し共通要素を1個ずつ合わせてk-1個の要素をもつ

    sq = Decimal(N * 8 + 1).sqrt()
    cond = sq % 2 == 1  # 奇数か

    if not cond:
        print('No')
        return
    k = int((1 + sq) // 2)  # Decimalのままだとrangeの引数に使えない
    print('Yes')
    print(k)

    deqs = []
    it = iter(range(1, N + 1))
    for _ in range(k):
        print(k - 1, end=' ')
        t = []
        for deq in deqs:
            x = deq.popleft()
            t.append(x)
        u = []
        for _ in range(k - 1 - len(t)):
            x = next(it)
            u.append(x)
        t.extend(u)
        print(*t) # *t,*uがRE
        deqs.append(deque(u))


if __name__ == '__main__':
    main()


Measured memory_bytes: 8592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
    int n; cin >> n;
    vector<string> S(n);
    for(int i=0; i<n; i++) cin >> S[i];
    int m; cin >> m;
    vector<string> T(m);
    for(int i=0; i<m; i++) cin >> T[i];

    int ans=0;
    for(int i=0; i<S.size(); i++){
        int tmp=0;
        tmp+=count(S.begin(), S.end(), S[i]);
        tmp-=count(T.begin(), T.end(), S[i]);
        ans=max(tmp,ans);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N = gets.to_i
B = gets.split.map(&:to_i)
A = Array.new(N, Float::INFINITY)

B.each_with_index do |b, idx|
  A[idx] = [A[idx], b].min
  A[idx + 1] = [A[idx + 1], b].min
end

puts A.inject(:+)


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
#define LINF 1e18
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int a, b; cin >> a >> b;
    int ans = 0;
    int cnt = 1;

    while (cnt < b) {
        ans++;
        cnt += a-1;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import numpy as np
from heapq import heappop, heappush


def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')

    can_go = False
    i = j = 1 # start
    c = 0     # real cost
    h = max(H - i, W - j) # goalまでの推定cost 
    s = c + h # score
    q = [] # open list
    heappush(q, (s, c, i, j))
    visited = set() # closed list
    # parent = [[None * (W + 1)] for _ in range(H+1)]

    while q:
        s, c, i, j = heappop(q)
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                visited.add((y, x))
                h = max(H - y, W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = (grid == '.').sum() - (c + 1)
    else:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 12548
#include <iostream>
#include<math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i =1; i <= (int)(n); i++)

int YKRD(int a,int b){
    int r = 0;
   r = a % b;
   while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
   return b;
}



int main() {
    int K;
    cin >>K;
    int X = 0;
    int Y = 0;
    long long ans = 0;
    rep(aa, K) {
        rep(bb, K) {
            rep(cc, K) {
                X = YKRD(aa, bb);
                Y = YKRD(cc, X);
                ans += Y;
            }
        }
    }

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

Measured memory_bytes: 3616
import java.util.Scanner;
public class Main {

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

    int a = scanner.nextInt();
    int b = scanner.nextInt();
    int c = scanner.nextInt();
    int ac = Math.abs(c-a);
    int ab = Math.abs(b-a);
    int bc = Math.abs(c-b);
    int d = scanner.nextInt();

    if ( ac <= d || (ab <=d && bc<=d) ) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 23124
import java.io.PrintWriter
import java.util.*

val pw = PrintWriter(System.out)
val sc = Scanner(System.`in`)

fun main(args: Array<String>) {
    val x = sc.nextLong()
    abc000a(x)
}

fun abc000a(x:Long) {
    var cnt = 0
    var now = 100L
    while(now < x){
        cnt += 1
        now = (now * 1.01).toLong()
    }
    println(cnt)
}


fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextListOfString() = next().split(" ")
fun nextListOfInt() = nextListOfString().map { it.toInt() }
fun nextListOfLong() = nextListOfString().map { it.toLong() }
fun nextListOfDouble() = nextListOfString().map { it.toDouble() }



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

typedef vector< vector<int> > vvi;
typedef vector< vector<bool> > vvb;
typedef vector< vector<char> > vvc;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef long long ll;

int main(){
    ll n,d;
    cin >> n >> d;
    vector<ll> x(n),y(n);
    for(int i=0;i<n;i++){
        cin >> x[i] >> y[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(x[i]*x[i]+y[i]*y[i]<=(d*d)) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;}
typedef long long ll;

int n,k,s,a;

int main() {
  cin >> n >> k >> s;
  s==1000000000 ? a=1 : a=s+1;
  rep(i,n){
    if(i<k)
    cout << s << endl;
    else    
    cout << a << endl;
  }
}

Measured memory_bytes: 1280