akhauriyash/Code-Regression huggingface dataset:
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
int read(char *s){
    R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));
    for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);
    return s[len+1]='\0',len;
}
double readdb()
{
    R double x=0,y=0.1,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(x=ch-'0';(ch=getc())>='0'&&ch<='9';x=x*10+ch-'0');
    for(ch=='.'&&(ch=getc());ch>='0'&&ch<='9';x+=(ch-'0')*y,y*=0.1,ch=getc());
    return x*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int P=998244353;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int inc(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
clock_t start=clock();
inline void ck(){
    if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
}
const int N=15;
double res;int id[N],x[N],y[N],n;
inline double calc(R int i,R int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
int main(){
	scanf("%d",&n);
	fp(i,1,n)scanf("%d%d",&x[i],&y[i]),id[i]=i;
	do{
		fp(i,1,n-1)res+=calc(id[i],id[i+1]);
	}while(next_permutation(id+1,id+1+n));
	fp(i,1,n)res/=i;
	printf("%.15lf\n",res);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] grid = new char[h][w];
		for(int i = 0; i < h; i++){
		    String s = sc.next();
		    grid[i] = s.toCharArray();
		}
		
		
		// 計算
		char[][] result = new char[h][w];
		for(int i = 0; i < h; i++){
		    Arrays.fill(result[i], '0');
		}
		int[] dx = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
		int[] dy = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
		for(int i = 0; i < h; i++){
		    for(int j = 0; j < w; j++){
		        if(grid[i][j] == '#'){
		            for(int k = 0; k < dx.length; k++){
		                int ni = i + dy[k];
		                int nj = j + dx[k];
		                if(0 <= ni && ni < h && 0 <= nj && nj < w){
		                    if(grid[ni][nj] != '#'){
		                        result[ni][nj] += 1;
		                    }else{
		                        result[ni][nj] = '#';
		                    }
		                }
		            }
		        }
		    }
		}
		
		// 出力
		for(int i = 0; i < h; i++){
		    String s = String.valueOf(result[i]);
		    System.out.println(s);
		}
	}
}



Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int x, y, a, b, c;
	std::cin >> x >> y >> a >> b >> c;
	long long int sol = 0;

	std::vector<long long int> red(a), green(b), blank(c);
	for (int i = 0; i < a; ++i) std::cin >> red[i];
	for (int i = 0; i < b; ++i) std::cin >> green[i];
	for (int i = 0; i < c; ++i) std::cin >> blank[i];

	sort(red.rbegin(), red.rend());
	sort(green.rbegin(), green.rend());
	sort(blank.rbegin(), blank.rend());
	int k = 0;
	int lastR = x - 1, lastG = y - 1;
	
	while (k < c && lastR >= 0 && lastG >= 0 && (blank[k] > red[lastR] || blank[k] > green[lastG])) {
		if (red[lastR] < green[lastG]) {
			--lastR;
			sol += blank[k];
			++k;
		}
		else {
			--lastG;
			sol += blank[k];
			++k;
		}
	}
	while (k < c && lastR >= 0 && blank[k] > red[lastR]) {
		--lastR;
		sol += blank[k];
		++k;
	}
	while (k < c && lastG >= 0 && blank[k] > green[lastG]) {
		--lastG;
		sol += blank[k];
		++k;
	}

	for (int i = 0; i <= lastR; ++i) sol += red[i];
	for (int i = 0; i <= lastG; ++i) sol += green[i];

	std::cout << sol << '\n';
return 0;
}

Measured memory_bytes: 2560
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld double 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define sl(a) a.size()
#define mod 1000000007 
#define lcm(a,b) (a*b)/__gcd(a,b)
#define MAX1 100006
#define f first
#define s second
#define pi 2*acos(0.0)
ll countDigit(long long n) 
{ 
    return floor(log10(n) + 1); 
} 
void solve()
{
    ll n,count=0; cin>>n;
    rep(i,1,n+1)
    {
        if((countDigit(i)&1)) count++;
    }cout<<count;
}
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt","r",stdin);
    //for getting error from error.txt
    freopen("error.txt", "w", stderr);
    // for writing output to output.txt
    freopen("output.txt","w",stdout);
    #endif
    BOOST
    int T=1;  //cin>>T;
    while(T--) solve();
    cerr<<"Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<"\n";
    cerr<<"My CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
    return 0;
}


Measured memory_bytes: 3944
#pragma GCC target ("avx2") 
#pragma GCC optimization ("O3") 
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define fast_az_fuk ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long 
#define int ll 
#define ull unsigned ll
#define ld long double 
#define pb push_back 
#define pf push_front
#define dll deque<ll> 
#define vll vector<ll> 
#define pll pair<ll,ll> 
#define mapll map<ll,ll>
#define endl "\n" 
#define all(v) v.begin(),v.end() 
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
void swap(auto*,auto*);
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    fast_az_fuk
    ll n; cin>>n; vll x; vll y;  for(ll i=0;i<n;i++) {
        ll u,v; cin>>u>>v; x.pb(u+v); y.pb(u-v);
    }
    sort(all(x));
    ll m1=abs(x[n-1]-x[0]);
    sort(all(y));
    ll m2=abs(y[n-1]-y[0]);
    cout<<max(m1,m2);
    return 0;
}
void swap(auto &a,auto &b)
{
    auto temp=a; a=b; b=temp;
}

Measured memory_bytes: 6612
#include <stdio.h>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;

int main(){
  
  /* read input */
  int N;
  scanf("%d", &N); // read int
  
  if(N == 25){
    printf("Christmas");
  }
  else if(N==24){
    printf("Christmas Eve");
  }
  else if(N==23){
    printf("Christmas Eve Eve");
  }
  else if(N==22){
    printf("Christmas Eve Eve Eve");
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int>>

using namespace std;

int main(){
    int a, b, c, d, i, j, k, l, n, ans, cnt;
    cin >> n >> d;
    int tmp = 2 * d + 1;
    cnt = 0;
    while(n > 0){
        n -= tmp;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
long long min(long long a, long long b){
  if(a>b) return b;
  else return a;
}

int main(void){
  int n;
  long long h[100005],dp[100005]={0};
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
  for(int i=2;i<n+1;i++){
    if(i==2) dp[i]=dp[i-1]+fabs(h[i]-h[i-1]);
    else dp[i]=min(dp[i-1]+fabs(h[i]-h[i-1]),dp[i-2]+fabs(h[i]-h[i-2]));
  }
  printf("%lld",dp[n]);
  return 0;
}

Measured memory_bytes: 3260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx=1e5+5;
const ll mod=1e9+7;
vector<int> a[maxx];
ll ans; int n,m;
ll A[maxx];
ll fpow(ll x,ll n){
    ll res=1;
    while (n)
    {
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n >>=1;
    }
    return res;
}
ll inv(ll x){return fpow(x,mod-2);}
void init(){
    A[0]=1;
    for(int i=1;i<=100000;i++){
        A[i]=A[i-1]*i%mod;
    }
}
ll work(ll x,ll y){
    if(y>x) return 0;
    if(y==x) return A[x];
    return A[x]*inv(A[x-y])%mod;
}
void dfs(int x,int fa,int dep){
    if(dep==0){
        ll sz=(ll)a[x].size();
        ans=ans*work(m-1,sz)%mod;
    }
    if(dep>=1){
        ll sz=(ll) a[x].size()-1;
        if(sz==0) return;
        ans=ans*work(m-2,sz)%mod;
    }
    for(auto t : a[x]){
        if(t==fa) continue;
        dfs(t,x,dep+1);
    }
}
int main(){
    init();
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y; scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    ans=m%mod;
    dfs(1,0,0);
    cout<<ans<<endl;
}

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


int main() {
	string a1;
	string b1;
	string c1;

	cin >> a1  ;
	a1.erase(a1.begin() + 1,a1.begin()+3);
	
	cin >> b1  ;
	b1.erase(b1.begin() + 0,b1.begin()+1);
	b1.erase(b1.begin() + 1,b1.begin()+2);
	
	cin >> c1  ;
	c1.erase(c1.begin() + 0,c1.begin()+2);
	string str3 = a1 + b1 + c1;
	cout << str3 << endl;
	
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};

fn main() {
  let a = read::<i32>();
  let b = read::<i32>();
  let c = read::<i32>();

  let tasks = vec![a, b, c];

  println!(
    "{}",
    tasks.iter().max().unwrap() - tasks.iter().min().unwrap()
  );
}



Measured memory_bytes: 4352
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

T = [V[i] - C[i] for i in range(N)]
T_max = 0
for i in range(N):
    if T[i] > 0:
        T_max += T[i]

print(T_max)

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



void print(vector<int> v){
	
	for(int i=0;i<v.size();i++){
		cout<<v[i];
	}
	//cout<<endl;
}
int jud(int x){
	
	if(x%2==0)return x/2;
	else return (3*x)+1;
}
int s;
int cnt=0;
int m[10000001]={0};
void solve(){
	
	cin>>s;
	m[s]+=1;
	int a=jud(s);
	m[a]+=1;
	for(int i=2;;i++){
	//cout<<a<<endl;
		a=jud(a);
		m[a]+=1;
		if(m[a]==2){
			cout<<i+1<<endl;
			return;
		}
		
	}

}


int main(){

    solve();
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
string map[300];
signed main() {
	int n;
	while (cin >> n, n) {
		for (int i = 0; i < n; i++)cin >> map[i];
		int ans = 0;
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				if (map[x][y] == '0')continue;
				int x1 = x, y1 = y;
				for (int i = -1; i <= 1; i++) {
					for (int j = -1; j <= 1; j++) {
						x1 = x; y1 = y;
						if (i == 0 && j == 0)continue;
						int cnt = 1;
						while (x1 + i >= 0 && x1 + i < n && y1 + j >= 0 && y1 + j < n) {
							if (map[x1 + i][y1 + j] != '1') goto heaven;
							x1 += i; y1 += j; cnt++;
						}
					heaven:
						ans = max(ans, cnt);
					}
				}
			}
		}
		cout << ans << endl;
	}
}


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

int main() {
  int N, Q;
  cin >> N;
  vector<int> A(N), B, C;
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  cin >> Q;
  B.resize(Q), C.resize(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> B[i] >> C[i];
  }

  map<long long, long long> m;
  for (int i = 0; i < N; ++i) {
    ++m[A[i]];
  }

  long long ans = 0;
  for (auto i : m) {
    ans += i.first * i.second;
  }

  for (int i = 0; i < Q; ++i) {
    ans += (C[i] - B[i]) * m[B[i]];
    cout << ans << endl;
    m[C[i]] += m[B[i]], m[B[i]] = 0;
  }
}


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

int main()
{
  int N, K, sum = 1;

  cin >> N >> K;

  for (int i = 0; i < N; i++)
  {
    if (K < sum)
    {
      sum += K;
    }
    else
    {
      sum *= 2;
    }
  }

  cout << sum << endl;
}

Measured memory_bytes: 256
// Problem : C - Half and Half
// Contest : AtCoder - AtCoder Beginner Contest 095
// URL : https://atcoder.jp/contests/abc095/tasks/arc096_a?lang=en
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)n;i++)
#define REP(i,n) for(int i=0;i<(int)n;i++)
#define ll long long
#define mod 1000000007
int lcm(int x,int y){
	return x/__gcd(x,y)*y;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    int cost1=a*x+b*y;
    c=c*2;
    int cost2=0;
    if(x<y){
    	cost2=min(c*x+(y-x)*b,y*c);
    }else{
    	cost2=min(c*y+(x-y)*a,x*c);
    }
    cout<<min(cost1,cost2)<<endl;
    return 0;
}


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

#if DEBUG && !ONLINE_JUDGE
    #include "/home/tushar_garg/Desktop/cpp/debug.h"
#else
    #define dbg(x...)
#endif

typedef     long long                            ll; 
typedef     pair<ll, ll>                         pl; 
typedef     vector<ll>                           vl;
typedef     vector<char>                         vc;
typedef     vector<bool>                         vb; 
typedef     vector<vl>                           vvl; 
typedef     vector<pl>                           vll; 
typedef     map<ll, ll>                          dict; 
typedef     map<ll, ll, greater <ll> >           sdict; 
typedef     map<char, ll>                        mcl;
typedef     priority_queue<ll>                   pqi;
typedef     priority_queue<pl>                   pqii;
typedef     priority_queue<ll, vl, greater<ll>>  pqmini;

#define rep(i, a, n) for (auto i=(a)-((a)>(n)); i!=(n)-((a)>(n)); i+=1-2*((a)>(n)))
#define trav(i, a) for(auto &i:a)
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back
#define eb emplace_back
#define flash ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define QuickSilver cin.exceptions(cin.failbit),setprecision(12),cout.precision(12);
#define fill(a, b) memset(a, b, sizeof(a)
#define get(a) rep(i,0,sz(a))cin>>a[i];
#define sz(a) (ll)(a.size())
#define all(a) a.begin(), a.end()
#define mod 1000000007

int main(){
	flash; QuickSilver;
	int n; cin>>n;
	vl a(n); get(a);
	vvl dp(n, vl(n, 1e18));
	vl pre(n+1,0); rep(i,0,n) pre[i+1]=pre[i]+a[i], dp[i][i]=0;
	rep(len,0,n)rep(i,0,n-len){
		int j=i+len;
		rep(k,i,j)
			dp[i][j]=min(dp[i][j],pre[j+1]-pre[i]+dp[i][k]+dp[k+1][j]);
	}
	cout<<dp[0][n-1]<<"\n";
}

Measured memory_bytes: 1536
#include <iostream>

int main (){
	int a,b,w;
	std::cin>>w>>a>>b;
	if(a>b){
		if(b+w>a)
			std::cout<<"0"<<std::endl;
		else
			std::cout<<a-(b+w)<<std::endl;
	}
	else{
		if(a+w>b)
			std::cout<<"0"<<std::endl;
		else
			std::cout<<b-(a+w)<<std::endl;
	}
	return 0;
}

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

int main(){
    int N;
    cin>>N;
    vector<vector<int> >G(N);
    vector<pair<int,int> >E_in;
    for(int i=1;i<N;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
        pair<int,int> p=make_pair(a,b);
        E_in.push_back(p);
    }

    queue<int> que;
    vector<int> used(N,0);
    vector<int> parent(N,0);
    int max_color=0;
    map<pair<int,int>,int>E_num;
    que.push(0);
    used[0]=1;
    while(que.size()!=0){
        int state=que.front();
        que.pop();
        int color_num=0;
        for(auto next:G[state]){
            if(used[next]!=1){
                color_num++;
                used[next]=1;
                if(color_num==parent[state]){
                    color_num++;
                }
                pair<int,int> p=make_pair(state,next);
                E_num[p]=color_num;
                parent[next]=color_num;
                que.push(next);
        }
    }
    max_color=max(max_color,color_num);
    
}
cout<<max_color<<"\n";
for (auto i:E_in){
    cout<<E_num[i]<<"\n";
}
return 0;
}


Measured memory_bytes: 13812
//
// Created by moono on 2018/10/27.
//

#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;



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

    //
    for (int i = 0; i < S.size(); ++i) {
        if(S[i] == 'B'){
            S[i] = '\0';

            //
            int j = i-1;
            while(S[j] == '\0' && j > 0){
                j--;
            }
            S[j] = '\0';
        }
    }

    //
    for (int i = 0; i < S.size(); ++i) {
        if(S[i] != '\0')
            cout << S[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;int*t,n,m,d,i,s[99999];main(){for(;cin>>d>>n>>m,s[i=n]=d;cout<<i<<endl){for(;--i;)cin>>s[i];for(sort(s,s+n);m--;t=upper_bound(s,s+n,d),i+=min(*t-d,d-t[-1]))cin>>d;}}

Measured memory_bytes: 1256
N, A = map(int, input().split())
X = [int(_) for _ in input().split()]
for i in range(N): #総和のみを考えるために全体からAを引く
    X[i] -= A

def DP(i, n, memo = {}): #i番目までのカードを使って総和をnにする組合せの数
    if i == 1:
        return (1 if X[0] == n else 0)
    try:
        return memo[(i, n)]
    except KeyError:
        ans = DP(i-1, n, memo) + DP(i-1, n-X[i-1], memo)
        if n == X[i-1]:
            ans += 1
        memo[(i, n)] = ans
        return ans

memo = {}
print(DP(N, 0, memo))

Measured memory_bytes: 5232
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    a,b = na()
    print(a*b)
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 61696
import numpy as np
H,W = map(int, input().split())
S = [[] for i in range(H)]
for i in range(H):
  S[i] = list(input())
S = np.array(S)
S = np.where(S=="#",0,1)

l = np.zeros((H,W))
l[:,-1] = S[:,-1]
r = np.zeros((H,W))
r[:,0] = S[:,0]
u = np.zeros((H,W))
u[-1] = S[-1]
d = np.zeros((H,W))
d[0] = S[0]

for i in range(W-2,-1,-1):
  l[:,i] = (l[:,i+1]+1)*S[:,i]
for i in range(1,W):
  r[:,i] = (r[:,i-1]+1)*S[:,i]
for i in range(H-2,-1,-1):
  u[i] = (u[i+1]+1)*S[i]
for i in range(1,H):
  d[i] = (d[i-1]+1)*S[i]

print(int(np.max(l+r+u+d-3)))


Measured memory_bytes: 231168
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

const int mod = 1e9 + 7;

using VL = vector<long long>;
using VVL = vector<VL>;

int n;
VVL connect;
VVL dp;  // ith nodeで j=0/1 -> 白/黒に対応

class SegmentTree
{
private:
	const long long mini = 0;
	int n;
	vector<long long> dat;
public:
	SegmentTree(int n_) {
		n = 1;
		while (n < n_) {
			n *= 2;
		}

		dat.assign(n * 2 - 1, mini);
	};
	~SegmentTree() {
		dat.clear();
	};

	void update(int k, long long val) {
		k += n - 1;
		dat[k] = val;
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = max(dat[k*2 + 1], dat[k*2 + 2]);
		}
	}

	long long query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return mini;
		}

		if (a <= l && r <= b) {
			return dat[k];
		} else {
			long long vl = query(a, b, k*2 + 1, l, (l+r)/2);
			long long vr = query(a, b, k*2 + 2, (l+r)/2, r);
			return max(vl, vr);
		}
	}

	// [a, b)の範囲での値
	long long query(int a, int b) {
		return query(a, b, 0, 0, n);
	}

	void show() {
		int i = 0;
		for (auto e: dat) {
			printf("%3d: %6lld\n", i, e);
			i++;
		}
	}
};

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

	vector<int> h(n), a(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		h[i]--;
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	// range maximum query
	SegmentTree st(n);

	for (int i = 0; i < n; i++) {
		long long x = st.query(0, h[i]);

		// printf("%d, %lld, %d, %lld\n", i, x, h[i], x + a[i]);
		st.update(h[i], x + a[i]);
	}
	auto ans = st.query(0, n);
	cout << ans << endl;

	// st.show();
	return 0;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  int L[M], R[M];

  for (int i = 0; i < M; i++) {
    cin >> L[i] >> R[i];
  }

  int maxL = 1, minR = 100000;
  for (int i = 0; i < M; i++) {
    if (maxL < L[i]) {
      maxL = L[i];
    }
    if (R[i] < minR) {
      minR = R[i];
    }
  }

  if (maxL > minR) {
    cout << 0 << endl;
  } else {
    cout << minR - maxL + 1<< endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int n,q;
string str;

int main() {
	cin >> n >> q;
	cin >> str;
	vector<pair<char,char> > arr(q);
	for(int i = 0; i < q; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	reverse(arr.begin(),arr.end());
	int l = 0;
	int r = n;
	for(pair<char,char> p : arr) {
		char al = p.first;
		char op = p.second;
		//cout << al << "," << op << endl;
		if(l<str.size() && str[l]==al && op=='L') {
			l++;
		}else if(l>0&&str[l-1]==al&&op=='R') {
			l--;
		}
		if(r>0 && str[r-1]==al && op=='R') {
			r--;
		}else if(r<str.size()&&str[r]==al&&op=='L') {
			r++;
		}
		//cout << l << "," << r << endl;
	}
	int ans = max(0,r-l);
	cout << ans << endl;

}


Measured memory_bytes: 900
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long 
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define pw(x) (1<<(x))
#define inf 1000000005
#define MOD 1000000007 
#define N 100005
#define M 1000003
#define LOG 19
#define KOK 250
#define EPS 0.0000001
using namespace std;

int n,x;
int s[N],dp[N],pt[N];
int res[205][205];

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

}

int add(int x,int y) {

	x+=y;

	if(x>=MOD) x-=MOD;
	if(x<0) x+=MOD;

	return x;

}

int main() {

	scanf("%d %d",&n,&x);

	for(int i=1;i<=n;i++) scanf("%d",&s[i]);

	sort(s+1,s+1+n);

	for(int i=0;i<=n+1;i++) {

		res[i][0]=1;

		for(int j=1;j<=n+1;j++) {

			res[i][j]=mul(res[i][j-1],i+j-1);

		}

	}

	int ptr=0;

	for(int i=0;i<=x;i++) {

		while(s[ptr+1]<=i && ptr+1<=n) ++ptr;

		pt[i]=ptr;

		if(ptr==0) dp[i]=i;

		for(int j=ptr;j>=1;j--) {

			int nm=i%s[j];

			dp[i]=add(dp[i],mul(dp[nm],res[pt[nm]+1][ptr-pt[nm]-1]));

		}

	}

	dp[x]=mul(dp[x],res[ptr+1][n-ptr]);

	printf("%d",dp[x]);

}

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

ll M;
ll dp[100009];
vector< vector<int> > G;
void dfs1(int c,int p=-1){//木DP
	dp[c] = 1;
	for(auto to : G[c])if(to != p){
		dfs1(to,c);
		(dp[c] *= dp[to]+1LL ) %= M;
	}
}
ll ans[100009];
void dfs2(int c,int p=-1){//木DPした結果から計算
	ans[c] = 1;
	for(auto to:G[c]) ( ans[c] *= dp[to]+1LL ) %= M;

	int n = G[c].size();
	vector<ll> l(n),r(n);
	for(int i=0;i<n;i++) l[i] = r[i] = ( dp[G[c][i]] + 1LL ) % M;
	for(int i=1;i<n;i++) ( l[i] *= l[i-1] ) %= M;
	for(int i=n-2;i>=0;i--) ( r[i] *= r[i+1] ) %= M;

	for(int i=0;i<n;i++)if(G[c][i] != p){
		dp[c] = 1;
		if(i) ( dp[c] *= l[i-1] ) %= M;
		if(i+1 < n) (dp[c] *= r[i+1]) %= M;
		dfs2(G[c][i],c);
	}
}

int main(){
	int N;
	cin >> N >> M;
	vector<int> x(N-1),y(N-1);
	for(int i=0;i<N-1;i++) cin >> x[i] >> y[i];
	for(int i=0;i<N-1;i++) x[i]--,y[i]--;
	G.resize(N);
	for(int i=0;i<N-1;i++){
		G[x[i]].push_back(y[i]);
		G[y[i]].push_back(x[i]);
	}
	dfs1(0);
	dfs2(0);
	for(int i=0;i<N;i++){
		cout << ans[i] << '\n';
	}

}




/*
このhamayanhamayanさんの記事が分かりやすい
https://www.hamayanhamayan.com/entry/2019/01/12/152428

全方位木DPをする。
dfs1で0を根として普通に木DPをする。
次に、dfs1で作ったDPを改変しながら、dfs2で全ての頂点を根として答えを計算する。
全方位木DPの様式であり、パターン化されている。
　
dfs1関数。
木DPは
dp[cu] := 頂点cuの部分木の塗り方において、頂点cuが黒色に塗られていて、黒色の頂点が全て連結である塗り方の組み合わせ
で作る。
更新式は頂点cuの子供をc1,...,cNとすると、dp[cu] = (dp[c1]+1)*...*(dp[cN]+1)である。+1しているのは、頂点c1が白である状態を示す（根が白ならば部分木は全て白色なので1通り）。
頂点0が黒である場合の答えはこれで求められる。
この関数が分からない場合は、全方位木DPの前に木DPを学ぶことを勧める。
　
dfs2関数。
全方位木DPをするが、大切なのは、
「『頂点cuの処理時はDPが頂点cuを根としたときの状態になっている』ことを保つこと」
具体的には頂点cuから頂点toに遷移するときは、dp[cu]を頂点toを親としたときの値に変換してから遷移する。
dp更新は、頂点cuの子供をc1, ..., cNとすると、dp[cu] = (dp[c1] + 1)*...*(dp[cN] + 1)という感じなので、例えばc3に遷移するときはdp[cu] = (dp[c1]+1)*(dp[c2]+1)*(dp[c4]+1)*...*(dp[cN]+1)*(dp[parent]+1)として遷移する。
この計算を高速に行うには
lft[i] := (dp[c1]+1)*...*(dp[ci]+1)
rht[i] := (dp[ci]+1)*...*(dp[cN]+1)
を予め計算すると、高速に計算可能。
*/

Measured memory_bytes: 20224
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

int main() {
  int n, c;
  scanf("%d %d", &n, &c);
  vvi d(c, vi(c));
  rep (i, c) {
    rep (j, c) {
      scanf("%d", &d[i][j]);
    }
  }
  vvi board(n, vi(n));
  vvi sumup(3, vi(c, 0));
  rep (i, n) {
    rep (j, n) {
      scanf("%d", &board[i][j]);
      board[i][j] -= 1;
      sumup[(i+j)%3][board[i][j]] += 1;
    }
  }

  int ans = INT_MAX;
  rep (i0, c) {
    int cnt0 = 0;
    rep (i, c) {
      cnt0 += sumup[0][i] * d[i][i0];
    }
    rep (i1, c) {
      if (i0 == i1) { continue; }
      int cnt1 = 0;
      rep (i, c) {
        cnt1 += sumup[1][i] * d[i][i1];
      }
      rep (i2, c) {
        if (i0 == i2 || i1 == i2) { continue; }
        int cnt2 = 0;
        rep (i, c) {
          cnt2 += sumup[2][i] * d[i][i2];
        }
        int cnt = cnt0 + cnt1 + cnt2;
        ans = min(ans, cnt);
      }
    }
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 1280
# Relative rela
import sys

n = int(input())
txy_list = [[int(n) for n in input().split()] for i in range(n)]
times_list = [txy_list[0][0]] + [txy_list[i+1][0] - txy_list[i][0] for i in range(n-1)]

before_x, before_y = 0, 0
for i, txy in enumerate(txy_list):
	t, x, y = txy
	rela_x, rela_y = x - before_x, y - before_y
	remaining = times_list[i] - (abs(rela_x) + abs(rela_y))
	if 0 <= remaining and remaining % 2 == 0:
		before_x, before_y = x, y
	else:
		print("No")
		sys.exit()
print("Yes")

Measured memory_bytes: 22832
#include <stdio.h>

int main (void)
{
int A,B,C;
B = 0;
C = 0;
 scanf("%d", &A);
 //printf("入力値 A=%d,B=%d\n",A,B);
for(int i = 1;i < 10;i++){
    for(int j = 1;j < 10;j++){
        B = i *j ;
        if(B == A){
            C = 1;
            break;
        }
        if(B == A){
            C = 1;
            break;
        }
    }
}

if(C == 1){
    printf("Yes");
}
else{
    printf("No");
}
 return 0;
}

Measured memory_bytes: 128
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    n = int(input())
    a = list(map(int,input().split()))
    dp = [[0]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in reversed(range(n-1)):
        for j in range(i+1,n):
            dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])

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

if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 136536
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
typedef vector<int> vi;
typedef long long ll;
int N;
string X;
string ans;
int zerocount=0;
int D;
bool changed[1005];
int main(void)
{
  memset(changed,false,sizeof(changed));
  cin >> N >> X >> D;
  ans=X;
  for(int i=0;i<int(X.size());i++)
    {
      if(X[i]=='0') zerocount++;
    }
  if(zerocount>=D)
    {
      for(int i=0;i<int(ans.size());i++)
	{
	  if(D==0) break;
	  if(ans[i]=='0') 
	    {
	      ans[i]='1';
	      D--;
	    }
	}
    }
  else
    {
      for(int i=0;i<int(ans.size());i++)
	{
	  if(ans[i]=='0') 
	    {
	      changed[i]=true;
	      ans[i]='1';
	    }
	}
      D-=zerocount;
      int now=int(ans.size()-1);
      while(D>0)
	{
	  if(!changed[now] && ans[now]=='1')
	    {
	      ans[now]='0';
	      D--;
	    }
	  now--;
	}
    }
  cout << ans << endl;
  return 0;
}



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

int main(){
    int N;
    cin >> N;
    N *= 2;
    vector<int>v(N);
    for(int i = 0; i < N; i++)cin >> v[i];
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i = 0; i < N; i+=2)ans += v[i];
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p , l , r;};

struct Node T[MAX];

int n;

//先行
void preParse(int u)
{
	if( u == NIL) return;
	printf(" %d",u);
	preParse(T[u].l);
	preParse(T[u].r);
}

//中間
void inParse(int u)
{
	if( u == NIL) return;
	inParse(T[u].l);
	printf(" %d",u);
	inParse(T[u].r);
}

//後行
void postParse(int u)
{
	if(u == NIL) return;
	postParse(T[u].l);
	postParse(T[u].r);
	printf(" %d",u);
}

int main()
{
	int i , v , l , r , root;
	scanf("%d",&n);
	
	for( i = 0; i < n; i++)
	{
		T[i].p = NIL;
	}
	
	for( i = 0; i < n; i++)
	{
		scanf("%d %d %d",&v,&l,&r);
		T[v].l = l;
		T[v].r = r;
		if( l != NIL) T[l].p = v;
		if( r != NIL) T[r].p = v;
	}
	
	for( i = 0; i < n; i++) if(T[i].p == NIL) root = i;
	
	printf("Preorder\n");
	preParse(root);
	printf("\n");
	printf("Inorder\n");
	inParse(root);
	printf("\n");
	printf("Postorder\n");
	postParse(root);
	printf("\n");
	
	return 0;
}



Measured memory_bytes: 2104
def main():
    s = list(map(int, list(input())))
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        temp = s[-(1+i)]*pow(10,i,2019)
        r[i] = (temp+r[i-1])%2019

    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    ans+=cts[0]

    print(ans)

main()
    

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

int main(){
  int N;
  cin >> N;
  vector<int> V(N);
  vector<int> C(N);
  for (int i = 0; i < N; i++) cin >> V[i];
  for (int i = 0; i < N; i++) cin >> C[i];
  int ans = 0;
  for (int i = 0; i < N; i++){
    if (V[i] > C[i]){
      ans += V[i] - C[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	scanf("%d %d %d",&a,&b);
	if(a>=13)
		printf("%d",b);
	else if(a>=6)
		printf("%d",b/2);
	else
		printf("0");
	return 0;
}

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

void CountingSort(vector<int> &A, vector<int> &B, vector<int> &C, int k) {
    C.resize(k + 1, 0);
    for (int i = 0; i < A.size(); ++i) {
        ++C.at(A.at(i));
    }
    for (int i = 1; i <= k; ++i) {
        C.at(i) += C.at(i - 1);
    }
    for (int i = 0; i < A.size(); ++i) {
        B.at(C.at(A.at(i)) - 1) = A.at(i);
        --C.at(A.at(i));
    }
    return;
}

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

    int n;
    cin >> n;
    vector<int> A(n);
    vector<int> B(n);
    vector<int> C;
    int maxA = 0;
    for (int i = 0; i < n; ++i) {
        cin >> A.at(i);
        maxA = max(maxA, A.at(i));
    }
    CountingSort(A, B, C, maxA);
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << B.at(i);
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 18724
H, W = map(int, input().split())

ans = H * W
ans = min(ans, 0 if not W % 3 else H, 0 if not H % 3 else W)

for a, b in ((H, W), (W, H)):
    tmp = (a // 3 * b, (a - a // 3) * (b // 2), (a - a // 3) * (b - b // 2))
    ans = min(ans, max(tmp) - min(tmp))
    tmp = ((a // 3 + 1) * b, (a - a // 3 - 1) * (b // 2), (a - a // 3 - 1) * (b - b // 2))
    ans = min(ans, max(tmp) - min(tmp))

print(ans)


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

ll min_dest_abs(const ll x, const ll k, const ll d) {
    if (!k) return x;

    if (d <= x) {
        const ll q = min(x / d, k);
        return min_dest_abs(x - q * d, k - q, d);
    }

    assert(d > x);
    return k % 2 ? d - x : x;
}

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

    ll x, k, d;
    cin >> x >> k >> d;
    cout << min_dest_abs(abs(x), k, d) << '\n';

    return 0;
}


Measured memory_bytes: 3524
#include <bits/stdc++.h>
#define int long long
#define ld long double

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector < string > a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    int ans = 0;
    for(int k = 0; k < n; ++k){
        int ok = 1;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(a[(i + k) % n][j] != a[(j + k) % n][i]){
                    ok = 0;
                    //cerr << i << " " << (j + k) % n << " " << k << "\n";
                }
                //cerr << a[i][(j + k) % n] << "";
            }
            //cerr << "\n";
        }
        //cerr << "\n\n";
        ans += ok * n;
    }
    cout << ans << "\n";
}




signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        cin >> t;
    #endif
    for(int i = 0; i < t; ++i){
        solve();
    }
}


Measured memory_bytes: 384
from operator import itemgetter
N,M = map(int,input().split())
graph = [[int(i) for i in input().split()] for _ in range(M)]
graph.sort(key=itemgetter(1))
ans = 0
cut = 0

for i in range(M):
    if cut < graph[i][0]:
        cut = graph[i][1] -1
        ans += 1

print(ans)


Measured memory_bytes: 22888
fun main(args: Array<String>) {
    val (n, a) = readLine()!!.split(" ").map { it.toInt() }
    var inputs = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    // N 枚の inputs から 任意の枚数を選んで平均を a にしたい
    // 何通りあるか？
    // 動的計画法

    // 目標平均値からの差分に直す
    val diffs = inputs.map { it - a }

    // 二次元 dp
    // どんな前提があれば答えを出せるか　を考える ( i 枚目まで考えたときに合計が j になっているパターン数 -> i+1 枚目までで考えたときの合計が j になっているパターン数
    // dp[i][j] = dp[i-1][j-xi] + dp[i-1][j] かと
    // j は -50*50 ~ 50*50 で出せば良い & i も ~ 50 -> 5000 * 50 = 250000 のメモ配列

    // i = 0 の場合の行を追加， j = 2500 が合計 0 に対応
    val dp = Array(51) { LongArray(5001) { 0 } }
    dp[0][2500] = 1

    // WA: input のインデックスも dp に合わせて 1スタートにしなくてはいけない
    // WA: diffs ではなく inputs を使ってしまっていた omg
    val diffsReIndexed = mutableListOf(0)
    diffsReIndexed.addAll(diffs)

    // WA: dp のインデックスがうまく合わせづらい
    // -2500 ~ 2500 を 0 ~ 5000 にシフトした状態で答えを求める
    // 更新される値が 2500 番目付近に入るため，デバッガーで確認しづらい -> これが一番の問題・・・
    // 負のインデックスを考えたほうがやりやすいか？？ 結局同じか
    for (i in 1 until n + 1) {
        for (j in 0 until 5001) {

            // println("$i $j")
            // WA: インデックスが 0 以上の場合しか考慮しておらず 5001 以上になる場合を考慮できていなかった
            if (j-diffsReIndexed[i] in 0..5000 ) {
                dp[i][j] = dp[i-1][j-diffsReIndexed[i]] + dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

//    // デバッグ出力
//    for (i in 0 until n+1) {
//        for ( j in 0 until 5001) {
//            if(dp[i][j] > 0) {
//                println("$i $j")
//                println(dp[i][j])
//            }
//        }
//    }

    // WA: 何故か答えが 1 大きい -> 最初の 0 枚で 0 のときに初期値として入れた 1 が影響している
    // dp として答えを出す際には必要だが，最終的な答えからは差し引く必要がある
    println(dp[n][2500] - 1)
}

Measured memory_bytes: 40972
n,m,c=gets.split.map(&:to_i)
b=gets.split.map(&:to_i)
a=n.times.map{gets.split.map(&:to_i)}

ans=0
a.each{|q|
  temp=c
  m.times{|i|temp+=q[i]*b[i]}
  ans+=1 if temp>0
}

puts ans

Measured memory_bytes: 1788
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

struct Mod {
    static ll BASE;
    ll value = 0;
    static ll residue(ll value) { return (value % BASE + BASE) % BASE; }
    Mod(ll value)
    : value(residue(value)) {}
    Mod operator+(const Mod& rhs) const { return Mod(value + rhs.value); }
    void operator+=(const Mod& rhs) { *this = *this + rhs; }
    Mod operator-(const Mod& rhs) const { return Mod(value - rhs.value); }
    void operator-=(const Mod& rhs) { *this = *this - rhs; }
    Mod operator*(const Mod& rhs) const { return Mod(value * rhs.value); }
    void operator*=(const Mod& rhs) { *this = *this * rhs; }
};
ll Mod::BASE = 1000000007;

ll N;
vector<vector<ll>> aij;
vector<ll> dp;

ll score(ll group) {
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = i+1; j < N; j++) {
            if (((group & ((ll)1 << i)) != 0) && ((group & ((ll)1 << j)) != 0)) {
                ans += aij[i][j];
            }
        }
    }
    return ans;
}

void exec_dp(ll subset) {
    if (dp[subset] != numeric_limits<ll>::min()) {
        return;
    }
    ll first_bit = -1;
    while (true) {
        first_bit++;
        if (subset & ((ll)1 << first_bit)) {
            break;
        }
    }
    ll rest = subset - ((ll)1 << first_bit);
    ll rest_sub = rest;
    do {
        exec_dp(rest_sub);
        dp[subset] = max(dp[subset], dp[rest_sub] + score(subset - rest_sub));
        rest_sub = (rest_sub - 1) & rest;
    } while (rest_sub != rest);
}

int main() {
    cin >> N;
    aij = make_vec_nd((ll)0, N, N);
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            ll elem;
            cin >> elem;
            aij[i][j] = elem;
        }
    }
    dp = make_vec_nd(numeric_limits<ll>::min(), 1 << N);
    dp[0] = 0;
    exec_dp(((ll)1 << N) - 1);
    cout << dp[((ll)1 << N) - 1] << endl;
}



Measured memory_bytes: 768
#include <bits/stdc++.h>
#define inf (long long)(1e17)
using namespace std;
using P = pair<int, int>;

long long n, m;
vector<long long> a;
vector<vector<long long>> l, r;

long long solve();

int main() {
  cin >> n >> m;
  a.resize(n);
  for (auto &p : a) cin >> p;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0, sum = 0, now = 0, cnt = 0;
  for (auto &p : a) --p;
  l.resize(m);
  r.resize(m);
  for (int i = 1; i < n; ++i) {
    long long nowl = (a[i - 1] + 1) % m, nowr = a[i];
    l[nowr].push_back(nowl);
    r[nowl].push_back(nowr);
    sum += (nowr + m - nowl + 1) % m;
    if (a[i - 1] > a[i]) now += m - 1 - a[i - 1], cnt += (a[i - 1] != m - 1);
  }
  for (int i = 0; i < m; ++i) {
    res = max(res, now);
    for (auto p : l[i]) {
      now -= (i + m - p) % m;
      --cnt;
    }
    cnt += r[i].size();
    now += cnt;
  }
  return sum - res;
}

Measured memory_bytes: 13460
#include <bits/stdc++.h>
#define N 200020
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?x:-x;
}
ll a[N], sum, ans = 1ll << 60;
int main(int argc, char const *argv[]) {
	int n = read();
	for (int i = 1; i <= n; i++)
		sum += a[i] = read();
	for (int i = 1; i < n; i++) {
		a[i] += a[i - 1];
		ans = min(ans, abs(a[i] * 2 - sum));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h> 
using namespace std;
#define  LL long long int
int main() 
{ 

    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    LL N,M,K;
    cin>>N>>M>>K;
    vector< vector<char> > arr(N,vector<char>(M));
    for(LL i=0;i<N;i++)
    {
        for(LL j=0;j<M;j++)
        {
            cin>>arr[i][j];
        }
    }
    LL count=0;
    vector<LL> row(N,0);
    vector<LL> col(M,0);
    for(LL i=0;i<N;i++)
    {
        for(LL j=0;j<M;j++)
        {
            if(arr[i][j]=='#')
            {
                count+=1;
                row[i]+=1;
                col[j]+=1;
            }
        }
    }
    LL ans=0;
    LL BitMaskR=(1<<N)-1;
    LL BitMaskC=(1<<M)-1;
    for(LL i=0;i<=BitMaskR;i++)
    {
        for(LL j=0;j<=BitMaskC;j++)
        {
            vector<LL> r;
            vector<LL> c;
            for(LL k=0;k<31;k++)
            {
                if((i&(1<<k)))
                {
                    r.push_back(k);
                }
            }
            for(LL k=0;k<31;k++)
            {
                if((j&(1<<k)))
                {
                    c.push_back(k);
                }
            }
            LL s=0;
            for(auto it:r)
            {
                for(auto k:c)
                {
                    if(arr[it][k]=='#')
                        s-=1;
                }
            }
            for(auto it:r)
                s+=row[it];
            for(auto it:c)
                s+=col[it];
            if(count-s==K)
                ans++;
        }
    }
    cout<<ans<<endl;
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int res = min(b / a, c);
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3628
import sys
input=sys.stdin.readline
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
if M -N >= 2019 or (N % 2019) > (M % 2019):
    print(0)
else:
    N = N % 2019
    M = M % 2019
    Min = 2019
    for i in range(N,M):
        for j in range(i+1,M+1):
            c = (i * j ) % 2019
            if c < Min:
                Min = c
    print(Min)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(void){
    int n;
    std::cin >> n;
    int max = 0;
    int next = 0;
    int maxi = 0;
    int nexti = 0;
    for(int i = 0; i < n; i++) {
        int now = 0;
        std::cin >> now;
        if(now >= max) {
            next = max;
            nexti = maxi;
            max = now;
            maxi = i;
        } else if(now >= next) {
            next = now;
            nexti = maxi;
        }
    }
    for(int i = 0; i < n; i++) {
        int result = i == maxi ? next : max;
        std::cout << result << std::endl;
    }
}


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

#define ll long long
#define ull unsigned long long 

int main(){
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll> > a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i].first >> a[i].second;

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

    ll t=0;
    for(int i=0; i<n && m>0; ++i){
        t += a[i].first * ((a[i].second > m)?m:a[i].second);
        m -= a[i].second;
    }
    cout << t;
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  while (cin >> n >> m, n) {
    vector<int> a(21), b(21);
    while (n--) {
      int h;
      cin >> h;
      ++a[h];
    }
    while (m--) {
      int h;
      cin >> h;
      ++b[h];
    }
    int res = 0;
    for (int i = 1; i <= 20; ++i) {
      res += i * max(a[i], b[i]);
    }
    cout << res << '\n';
  }
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n,x,t;
    cin>>n>>x>>t;
    if(n%x==0) cout<<(n/x)*t;
    else cout<<((n/x)+1)*t;
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main()
{
	int n;
	long long arr[55];
	long long sum = 0, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> arr[i];
		sum += arr[i];
		ans -= arr[i] * arr[i];
	}
	ans += sum * sum;
	cout << ans / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;


int neutral = 0;
int incr = 1;
int decr = -1;

int main() {

    int N;
    long C;
    long K;
    cin >> N >> C >> K;

    vector<long> ts;

    for (int i = 0; i < N; i++) {
        int t;
        cin >> t;
        ts.push_back(t);
    }


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

    int count = 0;

    for (int i = 0; i < N;) {

        int c = C;

        int t = ts[i];

        int j = i;

        while ((t <= ts[j]) and (ts[j] <= t + K) and (c > 0)) {
            j += 1;
            c -= 1;
        }

        i = j;
        count += 1;
    }

    cout << count << "\n";

    return 0;

}

Measured memory_bytes: 1400
import itertools
N,M=map(int,input().split())
edges = {tuple(map(int,input().split())) for _ in range(M)}
paths = itertools.permutations(range(2,N+1))
ans = 0
for path in paths:
    count = 0
    path = [1]+list(path)
    for edge in zip(path[:-1],path[1:]):
        count += tuple(sorted(edge)) in edges
    ans += count==N-1
print(ans)

Measured memory_bytes: 41452
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    ll n; cin>> n;
    map<string, ll> m;
    vector<string> s(n);
    ll ans=0;
    rep(i, n){
        cin>> s[i];
        sort(s[i].begin(), s[i].end());
        m[s[i]]++;
        if(m[s[i]] != 1) ans += m[s[i]] -1;
    }

    cout<< ans << endl;
}

Measured memory_bytes: 13972