akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll hell=998244353,dp[305][90005][2];
ll exp(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y&1)
        res=(res*x)%hell;
        y>>=1;
        x=(x*x)%hell;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,sum=0,s=0;
    cin>>n;
    ll arr[n+1];
    for(ll i=1;i<=n;i++){
        cin>>arr[i];
        s+=arr[i];
    }
    sort(arr+1,arr+n+1);
    dp[0][0][0]=dp[0][0][1]=1;
    for(ll i=1;i<=n;i++)
    for(ll j=0;j<=s;j++){
        dp[i][j][0]=dp[i-1][j][0];
        dp[i][j][1]=(dp[i-1][j][1]*2)%hell;
        if(j>=arr[i]){
            dp[i][j][0]+=dp[i-1][j-arr[i]][0];
            dp[i][j][1]+=dp[i-1][j-arr[i]][1];
            dp[i][j][1]%=hell;
            dp[i][j][0]%=hell;
        }
    }
    ll res=exp(3,n);
    for(ll i=(s+1)/2;i<=s;i++){
        res+=(hell-(3*dp[n][i][1])%hell);
        res%=hell;
    }
    if(s%2==0){
        res+=(3*dp[n][s/2][0])%hell;
        res%=hell;
    }
    cout<<res;
}


Measured memory_bytes: 422912
import std.stdio;
import std.conv;
import std.array;

void main()
{
    long N = readln.split[0].to!long;
    long[] T = new long[5];
    foreach (i; 0..5){
        T[i] = readln.split[0].to!long;
    }

    long minT = T[0];
    foreach (t; T){
        if (t < minT) minT = t;
    }

    long ans = N / minT;
    if (N % minT) ans++;
    ans += 4;

    writeln(ans);
}



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

int h, w;
vector<string> v;
int d[50][50];
int inf = 1e9+7;
typedef pair<int, int> P;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int main(){
	cin >> h >> w;
	for(int i=0; i<h; ++i){
		string s;
		cin >> s;
		v.push_back(s);
	}
	for(int i=0; i<h; ++i)
		for(int j=0; j<w; ++j)
			d[i][j] = inf;
	d[0][0] = 0;
	queue<P> q;
	q.push(P(0, 0));
	while(!q.empty()){
		P p = q.front();
		q.pop();
		for(int i=0; i<4; ++i){
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];
			if(0 <= nx && nx < h && 0 <= ny && ny < w && v[nx][ny] == '.' && d[nx][ny] > d[p.first][p.second] + 1){
				d[nx][ny] = d[p.first][p.second] + 1;
				q.push(P(nx, ny));
			}
		}
	}
	int tmp = 0;
	for(int i=0; i<h; ++i)
		for(int j=0; j<w; ++j)
			if(v[i][j] == '#')
				++tmp;
	if(d[h-1][w-1] == inf) cout << -1 << endl;
	else cout << h*w-tmp-d[h-1][w-1]-1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        String ans = s + "s";
        if(s.endsWith("s")) {
            ans = s + "es";
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 38504
n,m=map(int,input().split())
S=input()
T=input()

flag=True
import fractions
gcdnm=fractions.gcd(n,m)
lcmnm=(n*m)//gcdnm

nn=n//gcdnm
mm=m//gcdnm

for i in range(gcdnm):
    if S[i*nn]!=T[i*mm]:
        flag=False

if flag==True:
    print(lcmnm)
else:
    print(-1)
        

Measured memory_bytes: 5304
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

int main()
{
    int p, q, r;
    cin >> p >> q >> r;

    int minAns = min(p + q, q + r);
    minAns = min(minAns, r + p);
    cout << minAns << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> ga[100010];
int dp[100010];
bool vis[100010];
int dfs(int u){
	if(vis[u]==true)
	   return dp[u];
	else
	   vis[u]=true;
	for(int i=0;i<ga[u].size();i++){
		int v=ga[u][i];
		dp[u]=max(dp[u],dfs(v)+1);
	}
	return dp[u];
}
int main()
{
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++){
	    cin>>a>>b;
		ga[a].push_back(b);
	}
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++)
	   dfs(i);
	int maxx=0;
	for(int i=1;i<=n;i++)
	   maxx=max(maxx,dp[i]);
	cout<<maxx<<endl;
	return 0;
}


Measured memory_bytes: 8192
/*
 * Created by  Ganzorig Batsaikhan 13.06.2019 14:38:41 Ulaanbaatar Standard Time
 * 
 */
#include <bits/stdc++.h>

using namespace std;

int main(){
	int a[3];
	for (int i = 0; i < 3; i++){
		scanf("%d", a + i);
	}
	sort(a, a + 3);
	printf("%d\n", a[0] + a[1]);
	return 0;
}

Measured memory_bytes: 256
from math import sin, cos, pi


a, b, theta = map(float, input().split())
theta *= pi / 180
s = 0.5 * a * b * sin(theta) 

print(s) 
print((a ** 2 + b ** 2 - 2 * a * b * cos(theta)) ** 0.5 + a + b)
print(2 * s / a) 


Measured memory_bytes: 5700
#include <stdio.h>
int search(int A[], int n, int key){
  int i=0;A[n]=key;
  while(A[i]!=key)i++;
  return i!=n;
}
int main(void){
  int i,n,A[10000+1],q,key,sum=0;
  scanf("%d",&n);
  for(i=0; i<n; i++)scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(search(A,n,key))sum++;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2068
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const A=input[0].split(' ')[0]-0;
  const B=input[0].split(' ')[1]-0;
  var gcm;
  var min,max;
  min=Math.min(A,B);
  max=Math.max(A,B);
  var temp;
  while(min>0){
    temp=min;
    min=max%min;
    max=temp;
  }
  console.log(A*B/max);

}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29532
#include<bitset>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, a, n) for(int i=(a);i<(int)(n);i++)
#define repc(i, a, n) for(int i=(a);i<=(int)(n);i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout<<(cond? "Yes":"No")<<endl;
#define YES(cond) cout<<(cond? "YES":"NO")<<endl;
#define DBG(str) cerr<<(str)<<endl;
int main() {
	int n, k;
	cin >> n >> k;
	vector<int>a(n);
	rep(i, 0, n)cin >> a[i];
	if (n <= k) {
		cout << 1;
		return 0;
	}
	
	int ans = ceil((double)(n-1) / (k-1));
	cout << ans;

	return 0;
}





Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices.ComTypes;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int input = int.Parse(Console.ReadLine());

            int sur = input % 1000;
            int ans = 0;

            if(sur > 0)
            {
                ans = 1000 - sur;
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 27524
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int h,w,c;
int table[10][10];

int nt[10][10];

void copy(){
	rep(i,h)rep(j,w)nt[i][j] = table[i][j];
}

vector<int> vi;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
bool used[10][10];

void clear(){
	rep(i,h)rep(j,w)used[i][j]=false;
}

void change(int y,int x,int pc,int nc){
	used[y][x] = true;	
	nt[y][x] = nc;
	rep(i,4){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny>=0 && ny<h && nx>=0 && nx<w){
			if(!used[ny][nx] && pc == nt[ny][nx])change(ny,nx,pc,nc);
		}
	}
	// rep(i,h){
	// 	rep(j,w)cout<<nt[i][j]<<" ";
	// 	cout<<endl;
	// }
}


void calc(int y,int x){
	used[y][x] = true;
	rep(i,4){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny>=0 && ny<h && nx>=0 && nx<w){
			if(used[ny][nx])continue;
			if(nt[ny][nx] == nt[y][x])calc(ny,nx);
		}
	}
}

ll solve(int cnt){
	if(cnt==5){
		// cout<<"!!!"<<endl;
		clear();
		calc(0,0);
		ll res = 0;
		rep(i,h)rep(j,w)res+=used[i][j];
		return res;
	} 
	// cout<<"!!!"<<cnt<<endl;
	clear();
	change(0,0,nt[0][0],vi[cnt]);
	return solve(cnt+1);
}

int main(){
	while(cin>>h>>w>>c && h+w+c){
		rep(i,h)rep(j,w)cin>>table[i][j];
		ll ans = 0;
		rep(i,6){
			vi.push_back(i+1);
			rep(j,6){
				vi.push_back(j+1);
				rep(k,6){
					vi.push_back(k+1);
					rep(l,6){
						vi.push_back(l+1);
						vi.push_back(c);
						copy();
						// cout<<"!";
						// rep(ii,vi.size())cout<<vi[ii];
						// cout<<endl;
						ans = max(ans,solve(0));
						vi.pop_back();
						vi.pop_back();
					}
					vi.pop_back();
				}
				vi.pop_back();
			}
			vi.pop_back();
		}
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 3124
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for(int i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
template <class T>  // chmax(max, a);
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> //chmin(min,a)
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
template<typename T>
bool all_same(vector<T> v1,vector<T> v2)
{
    sort(ALL(v1));
    sort(ALL(v2),greater<T>());
    return v1 == v2;
}
   
// g++ -std=c++11 prac.cpp
ll Max=-1e9,Min=1e9+1;

int main(){
    ll a,b,d,x=0,y=0,z,n,m,k,lank=1,w,sum=100000,sum2=0,ans=0;
    string s,t;
    bool ok=true;
    cin >> n >> a >> b >> s;   
    rep(i,s.size()){
        if(s[i]=='a'){
            if(a+b>x+y){
                x++;
                cout << "Yes" << endl;
            }
            else{
                cout << "No" << endl;
            }
        }
        else if(s[i] == 'b'){
            if((a+b > x+y) && lank <= b){
                lank++;
                y++;
                cout << "Yes" << endl;
            }
            else{
                cout << "No" << endl;
            }

        }
        else{
            cout << "No" << endl;
        }
    }
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

// vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

vector<int> divisor(int n) {
  vector<int> ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main() {
  int n;
  cin >> n;
  vector<int> la(n+1);
  la[0] = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> la[i];
  }
  vector<int> ans;
  for (int i = n; i > 0; --i) {
    if (la[i] == 0) continue;
    ans.push_back(i);
    vector<int> div = divisor(i);
    for (int d: div) {
      la[d] = 1 - la[d];
    }
  }
  cout << ans.size() << endl;
  for (int a: ans) {
    cout << a << " ";
  }
  cout << endl;
}


Measured memory_bytes: 2424
#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdio>//C的输入输出
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <bitset>//bitset可按位定义串
//比如：bitset <1000> all;定义一个1000位的串
#include <algorithm>//STL各种算法 比如 swap sort merge max min 比较
#include <numeric>//常用数字操作 一般和algorithm搭配使用
#include <functional>//STL定义运算函数（代替运算符）
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
#define LOCAL
#define zeros(a,n) memset(a,0,(n)*sizeof(a[0]))
const int modn = 1e9+7;
int mod(int x) { return x<0?x+modn:x<modn?x:x-modn; }
//inv [ i ] = (modn - modn/i)*inv[ modn%i ] %modn;
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int k;
    cin>>k;
    LL ans = 0;
    for(int i = 1; i <= k; ++i){
        for(int j = 1; j <= k; ++j){
            for(int l = 1; l <=k; ++l){
                ans += gcd(i, gcd(j,l));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3196
s = input()[::-1]

now = 0
while now < len(s):
    if s[now:now + 7] == 'dreamer'[::-1]:
        now += 7
    elif s[now:now + 6] == 'eraser'[::-1]:
        now += 6
    elif s[now:now + 5] == 'dream'[::-1]:
        now += 5
    elif s[now:now + 5] == 'erase'[::-1]:
        now += 5
    else:
        print('NO')
        exit()

print('YES')


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define pb push_back
#define long long long
#define pll pair < long , long >
#define vll vector < pll >
#define ml map < long , long >
#define mll map < pll , long >
#define x first
#define y second
#define vl vector < long >
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main()
{
    io
    long r,g;
    cin>>r>>g;
    cout<<2*g-r;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, Q;
vi G[MAX_N];
ll P[MAX_N];
ll ans[MAX_N];

void loop(int v, int p, ll sum) {
	sum += P[v];
	ans[v] = sum;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		loop(n, v, sum);
	}
}

void solve() {
	cin >> N >> Q;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].pb(b); G[b].pb(a);
	}
	rep(i, 0, Q) {
		int at, cost; cin >> at >> cost; at--;
		P[at] += cost;
	}
	loop(0, -1, 0);
	rep(i, 0, N) {
		cout << ans[i] << " ";
	}
	cout << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 43136
import java.util.Scanner;

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

	int A = scan.nextInt();
	int B = scan.nextInt();
	int C = scan.nextInt();
	int D = scan.nextInt();

	if(A+B > C+D){
	    System.out.println("Left");
	}else if(A+B == C+D){
	    System.out.println("Balanced");
	}else{
	    System.out.println("Right");
	}
    }
}


Measured memory_bytes: 21844
#include <cstring>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

int calc(int a, int b){
  int c = 0;
  int ret = 0;
  while(a > 0 || b > 0){
    const int aa = a % 10;
    const int bb = b % 10;
    ret += aa * bb + c;
    c = aa + bb + c < 10 ? 0 : 1;
    a /= 10; b /= 10;
  }
  return ret + c;
}

int dp[310][310];
int a[310];
int s[310];
int n;
int sum(int l, int r){
  return s[r - 1] - (l == 0 ? 0 : s[l - 1]);
}

int solve(int l, int r){
  if(l + 1 == r) return 0;
  if(dp[l][r] != -1) return dp[l][r];

  int ret = 1e9;
  for(int i = l + 1; i < r; i++){
    ret = min(ret, solve(l, i) + solve(i, r) + calc(sum(l, i), sum(i, r)));
  }

  return dp[l][r] = ret;
}

int main(){
  n = getInt();
  REP(i,n) a[i] = getInt();
  REP(i,n) s[i] = a[i] + (i == 0 ? 0 : s[i - 1]);
  memset(dp, -1, sizeof(dp));
  printf("%d\n", solve(0, n));
  return 0;
}

Measured memory_bytes: 1432
N, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(0, W-w+1):
        if dp[j+w] < dp[j] + v:
            dp[j+w] = dp[j] + v
print(max(dp))

Measured memory_bytes: 7940
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    getLine
    as <- getIntList
    print $ (length as) - solve as

solve as | fas == 0 = length as + 1
         | otherwise = fas
    where fas = (foldl f 1 as) - 1

f a b | a == b = a + 1
      | otherwise = a

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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

const ll mod = 1000000007;
//const ll mod = 998244353;

const int MAX_N = 200010;
ll fact[MAX_N],fact_inv[MAX_N],inv[MAX_N];

ll pow_mod(ll a,ll b) {
    ll ret;
    if (b < 0) ret = pow_mod(a,mod+b-1);
    else if (b == 0) ret = 1;
    else if (b == 1) ret = a;
    else {
        ll c = pow_mod(a,b/2);
        if (b%2) ret = (c*c)%mod*a%mod;
        else ret = c*c%mod;
    }
    return ret;
}

void create_table(int n) {
    fact[0] = 1;fact[1] = 1;
    for (int i = 2;i <= n;++i) fact[i] = fact[i-1]*i%mod;
    fact_inv[n] = pow_mod(fact[n],-1);
    for (int i = n;i > 0;--i) fact_inv[i-1] = fact_inv[i]*i%mod;
    for (int i = 1;i <= n;++i) inv[i] = fact_inv[i]*fact[i-1]%mod;
}

ll combi(ll a, ll b) {
    return fact[a]*fact_inv[b]%mod*fact_inv[a-b]%mod;
}

int main() {
    ll n,m,k;
    cin >> n >> m >> k;
    create_table(n*m);
    ll ans = 0;
    for (int i = 1;i < n;++i) (ans += i*m*m%mod*(n-i)%mod*combi(n*m-2,k-2)%mod) %= mod;
    for (int i = 1;i < m;++i) (ans += i*n*n%mod*(m-i)%mod*combi(n*m-2,k-2)%mod) %= mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <limits>
using namespace std;

int main(){
    int a[3];
    for(size_t i = 0; i < 3; i++)
    {
        cin >> a[i];
    }
    int counter_5 = 0;
    int counter_7 = 0;
    for(size_t i = 0; i < 3; i++)
    {
        if(a[i] == 5){
            counter_5++;
        }
        else if(a[i] == 7){
            counter_7++;
        }
    }
    if(counter_5 == 2 && counter_7 == 1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> set_t;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define SUM(v) accumulate(v.begin(),v.end(),lli(0))
#define rev(n,d) for(int i=n;i>=d;i--)
#define FOR0(n) for(int i=0;i<n;i++)
#define FOR(a,n) for(int i=a;i<n;i++)
#define FORQ(a,n) for(int i=a;i<=n;i++)
#define inf 1000000009
#define inff 0x3f3f3f3f
#define sz(a) int((a).size())
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define mem(ar,x) memset(ar,x,sizeof ar)
#define present(container, element) (container.find(element) != container.end())
#define max3(a,b,c) return (lli(a)>lli(b)?(lli(a)>lli(c)?a:c):(lli(b)>lli(c)?b:c))
#define max4(a,b,c,d) return (max3(a,b,c)>lli(d)?(max3(a,b,c)):d)
#define min3(a,b,c) return (lli(a)<lli(b)?(lli(a)<lli(c)?a:c):(lli(b)<lli(c)?b:c))
#define min4(a,b,c,d) return (max3(a,b,c)<lli(d)?(max3(a,b,c)):d)
typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<int,pii>ppii;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<pii>vpii;
const int N=200005;
int dr8[]={0,0,1,-1,1,1,-1,-1};
int dc8[]={1,-1,0,0,-1,1,-1,1};
int dr4[]={0,1,-1,0};
int dc4[]={1,0,0,-1};
lli bit[4*N];int n;
void add(int i, lli x) {
	while(i<N) bit[i] =max(bit[i], x), i |=(i+1);
}
lli find(int i) {
	lli s=0;
	while(i>0) s=max(s,bit[i]),i = (i & (i + 1)) - 1;
	return s;
}
int main(){
	fast
	cin>>n;
	mem(bit,0);
	lli h[n],c[n];lli dp[n+5];
	mem(dp,0);
	FOR0(n) cin>>h[i];
	FOR0(n) cin>>c[i];
	FOR0(n){
			lli f=find(h[i]);
			dp[h[i]]=max(dp[h[i]],f+c[i]);
			add(h[i],dp[h[i]]);
	}
	lli an=0;
	FORQ(1,n){
		an=max(an,dp[i]);
	}
	cout<<an;
}



Measured memory_bytes: 11264
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <string>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    string ps,qs;

    int tmp;
    rep(i,n){
        cin >> tmp;
        ps += to_string(tmp);
    }
    rep(i,n){
        cin >> tmp;
        qs += to_string(tmp);
    }

    
    map<string,int> mp;
    string str;
    int cnt = 0;

    vector<int> v(n);
    rep(i,n) v[i] = i+1;
    do {
        for(auto x : v){
            str += to_string(x);
        }
        //cout << str << endl;
        mp[str] = cnt;
        
        str = "";
        cnt++;
    } while( next_permutation(v.begin(), v.end()) );

    int AA = mp[ps];
    int BB = mp[qs];
    cout << abs(AA - BB) << endl;

    return 0;
}

Measured memory_bytes: 4608
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
while(true){
   if(arr.length==0)break;
   var a=arr.shift().split("");
   var b=arr.shift().split("");
   var ans=0;
   var cnt=0;
   for(var i=a.length-1;i>=0;i--){
      cnt++;
      var x=i;
      var max=0;
      for(var j=0;j<=cnt;j++){
         if(a[x]==b[j])max++;
         else{
            ans=Math.max(ans,max);
            max=0;
         }
         x++;
      }
   }
   var cnt=0;
   for(var i=b.length-1;i>=0;i--){
      cnt++;
      var x=i;
      var max=0;
      for(var j=0;j<=cnt;j++){
         if(b[x]==a[j])max++;
         else{
            ans=Math.max(ans,max);
            max=0;
         }
         x++;
      }
   }
   console.log(ans);
}

Measured memory_bytes: 20576
from sys import stdin
inp = lambda : stdin.readline().strip()


def dfs_iter(n):
    stack = [n]
    ans = 0
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            ans += 1
            for child in adj[node]:
                if not visited[child]:
                    stack.append(child)
    return ans

n, m = [int(x) for x in inp().split()]
adj = [set() for i in range(n)]
visited = [False]*n
for i in range(m):
    u, v = [int(x) for x in inp().split()]
    adj[u - 1].add(v - 1)
    adj[v - 1].add(u - 1)
ans = 0
for i in range(n):
    if not visited[i]:
        ans = max(ans, dfs_iter(i))
print(ans)

Measured memory_bytes: 154488
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N, K, X, b[41];
vector<int> kb ={-1};
int main(){
    cin >> N >> K;
    for(int i = 0; i < 40; i++){
        if((K >> i) & 1) kb.push_back(i);
    }
    for(int i = 0; i < N; i++){
        ll A;
        cin >> A;
        for(int j = 0; j < 40; j++){
            if((A >> j) & 1) b[j]++;
        }
    }
    vector<ll> plu[4];
    for(int i = 0; i < kb.size() - 1; i++){
        ll p = 0;
        for(int j = kb[i] + 1; j < kb[i + 1]; j++){
            p += max(b[j], N - b[j]) * ((ll)1 << j);
        }
        plu[0].push_back(p);
        
        p = b[kb[i + 1]] * ((ll)1 << (kb[i + 1]));
        plu[1].push_back(p);

        p = 0;
        for(int j = kb[i] + 1; j < kb[i + 1]; j++){
            p += b[j] * ((ll)1 << j);
        }
        plu[2].push_back(p);

        p = (N - b[kb[i + 1]]) * ((ll)1 << (kb[i + 1]));
        plu[3].push_back(p);
    }

    ll ans = 0;
    for(int i = plu[1].size();i >= 0; i--){
        ll res = 0;
        for(int j = plu[1].size() - 1; j >= i; j--){
            res += plu[3][j] + plu[2][j];
        }
        if(i != 0) res += plu[1][i - 1] + plu[0][i - 1];

        for(int j = 0; j < i - 1; j++){
            res += max(plu[1][j], plu[3][j]);
            res += plu[0][j];
        }
        ans = max(ans, res);
    }
    for(int i = kb[kb.size() - 1] + 1; i < 40; i++){
        ans += b[i] * ((ll)1 << i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
D,G = map(int,input().split())
P,C = map(list,zip(*[list(map(int,input().split())) for i in range(D)]))
Solved = []
for i in range(2**D):
    bit = bin(i)[2:].zfill(D)
    solved = 0
    score = 0
    for j in range(D):
        if bit[j] == '1':
            score += (j+1)*100*P[j]+C[j]
            solved += P[j]
    if G-score > 0:
        for j in range(D):
            if bit[-j-1] == '0':
                for k in range(P[-j-1]-1):
                    score += (D-j)*100
                    solved += 1
                    if G-score <= 0:
                        break
            if G-score <= 0:
                break
    if G-score <= 0:
        Solved += [solved]
print(min(Solved))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll max_val = 1e5;
int main(){
	ll n,w,a,b;
	cin>>n>>w;
	vector<ll> val,wgt;
	for(int i=0;i<n;i++){
        cin>>a>>b;
        wgt.pb(a);
        val.pb(b);
	}
	vector<vector<ll>> dp(n+1,vector<ll>(max_val+1));
	for(int i=0;i<=n;i++){
        dp[i][0]=0;
	}
	for(int i=0;i<=max_val;i++){
        dp[0][i]=2*1e9;
	}
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
        for(int j=1;j<=max_val;j++){
            if(j>=val[i-1])
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-val[i-1]]+wgt[i-1]);
            else
                dp[i][j]=dp[i-1][j];
        }
	}
	ll ans= 0 ;
	for(ll i=max_val;i>=0;i--){
        if(dp[n][i]<=w){
            ans=i;
            break;
        }
	}
	cout<<ans<<endl;
  	return 0;
}


Measured memory_bytes: 83232
import java.util.*;

class Main{
	
	public static void main(String args[]){

		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int ar[] = new int[S.length()];
		for(int s=0;s<S.length();s++){
			if(S.charAt(s) == 'B')
				ar[s] = 0;
			else {
				ar[s] = 1;
			}
		}
		long div = 0;
		long ans = 0;
		for(int s=0;s<S.length();s++){
			if(ar[s] == 0){
				div++;
			}else{
				ans += div;
			}

		}
		System.out.println(ans);

	}
}

Measured memory_bytes: 26680
/**Bismillahir Rahmanir Rahim.**/
/*
         Md.Fagun Molla
         18ICTCSE006
         BSMRSTU(SHIICT)
*/
#include <bits/stdc++.h>
using namespace std;


#define  gcd(a,b)         __gcd(a,b)
#define  lcm(a,b)         (a*b)/gcd(a,b)
#define  ll               long long
#define  vi               std::vector<int>
#define  pb               push_back
#define  MAX              100007
#define  End              return 0;
#define                   pi acos(-1)


int main () {
    ll n,r;
    cin>>n>>r;
    ll c=0;
    while(n!=0){
        n/=r;
        c++;
    }
    cout<<c<<endl;
    End;
}
/* pray for me
All is well
*/





Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_v<T>(ts...)); }
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }

template<class T, class ...Tail>
void tiedSort(vector<T> &a, vector<Tail>&... tail) {
	int n = a.size();
	using S = tuple<T, Tail...>;
	vector<S> s(n);
	for (int i = 0; i < n; i++)
		s[i] = make_tuple(a[i], tail[i]...);
	sort(s.begin(), s.end());
	for (int i = 0; i < n; i++)
		tie(a[i], tail[i]...) = s[i];
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> L(N), R(N); rep(i, 0, N) {
		cin >> L[i] >> R[i];
		L[i]--;
	}

	tiedSort(L, R);

	auto maxLe = max_element(all(L));
	auto minRe = min_element(all(R));
	dump(L);
	dump(R);

	int ans = 0;

	multiset<int> l(all(L)), r(all(R));
	rep(i, 0, N) {
		l.erase(l.lower_bound(L[i]));
		r.erase(r.lower_bound(R[i]));
		chmax(ans, R[i] - L[i] + max(0ll, *r.begin() - *l.rbegin()));
		l.insert(L[i]);
		r.insert(R[i]);
	}
	dump(ans);
	int lb = maxLe - L.begin();
	int rb = minRe - R.begin();
	dump(lb, rb);
	if (lb != rb) {
		l.clear(); r.clear();
		rep(i, 0, N) {
			if (i == rb)continue;
			r.insert(R[i]);
		}
		l.insert(L[rb]);
		chmax(ans, max(0ll, R[rb] - *l.rbegin()) + max(0ll, *r.begin() - L[lb]));
		rep(i, 0, N) {
			if (i == lb)continue;
			if (i == rb)continue;
			dump(i, vector<int>(all(l)), vector<int>(all(r)));
			r.erase(r.lower_bound(R[i]));
			l.insert(L[i]);
			chmax(ans, max(0ll, R[rb] - *l.rbegin()) + max(0ll, *r.begin() - L[lb]));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 11236
#include<stdio.h>

int main(void){
    int K=0,A=0,B=0,C=0;
    long long ans=1;
    scanf("%d %d %d",&K,&A,&B);
    C=B-A;


    if(B-A<=2){
        printf("%d",K+1);
        return 0;
    }
    K-=A-1;
    ans+=A-1;

    if(K%2){
        K--;
        ans++;
    }
    
    for(int i=0;i<K/2;i++){
        ans+=C;
    }

    printf("%lld",ans);
    

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
using namespace std;
//const int MOD = pow(10, 9) + 7;
const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
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;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}

int modinv(int a, int m)
{
  int b = m, x = 1, y = 0;
  while (b > 0)
  {
    int q = a / b, r = a - q * b, s = x - q * y;
    a = b; b = r;
    x = y; y = s;
  }
  return mod(x, m);
}

class combination
{
public:
  vector<int> fac, finv, inv;

  combination(int M)
  {
    fac = vector<int>(M, 1);
    finv = vector<int>(M, 1);
    inv = vector<int>(M, 1);

    for (int i = 2; i < M; i++)
    {
      fac.at(i) = fac.at(i - 1) * i % MOD;
      inv.at(i) = MOD - inv.at(MOD % i) * (MOD / i) % MOD;
      finv.at(i) = finv.at(i - 1) * inv.at(i) % MOD;
    }
  }

  int COM(int N, int K)
  {
    if (N < K) return 0;
    if (N < 0 || K < 0) return 0;
    return fac.at(N) * (finv.at(K) * finv.at(N - K) % MOD) % MOD;
  }
};

signed main()
{
  int N, A, B, K;
  cin >> N >> A >> B >> K;
  
  combination cmb(300100);

  int ans = 0;
  for (int i = 0; i <= N; i++)
  {
    int j = (K - A * i) / B;
    if (j < 0 || N < j || A * i + B * j != K) continue;

    ans += cmb.COM(N, i) * cmb.COM(N, j) % MOD;
    ans %= MOD;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 7296
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int,int>
#define p64 pair<ll,ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream& operator<<(ostream& out, const pair<T,U>& p){
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename ...Args>
void print_container(const ContainerType<ValueType, Args...>& c){
	cout << "{ ";
	for(const auto& v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

int n;
int dig_n;

int get_first_digit(int x){
	int a = floor(log10(x) + 1);
	int ans = x / pow(10,a - 1);
	return ans;
}

int get_last_digit(int n){
	return (n % 10);
}

int get_val(int a,int b,int x){
	if(a == 0) return 0;
	int aRes = pow(10,x - 1);
	int num = pow(10,x - 2) - 1;
	int temp = a * aRes + num * 10 + b;
	while(temp > n && num >= 0){
		num--;
		temp = a * aRes + num * 10 + b;
	}
	if(num < 0) return 0;
	else return (num + 1);
}

void solve()
{
	cin >> n;
	dig_n = floor(log10(n) + 1);
	ll ans1 = 0;
	for(int i = 1;i < n + 1;i++){
		int dig_i = floor(log10(i) + 1);
		int ans = 0;
		for(int len = dig_n;len >= 3;len--){
			ans += get_val(get_last_digit(i),get_first_digit(i),len);
		}
		int z = get_first_digit(i);
		int x = get_last_digit(i);
		if(x == 0) continue;
		if(dig_i == 1){
			ans++;
			int y = x * 10 + z;
			if(y <= n) ans++;
		}
		else{
			if(z == x) ans++;
			int y = x * 10 + z;
			if(y <= n) ans++;
		}
		ans1 += ans;
	}
	cout << ans1 << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	clock_t start,stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for(int tc = 1;tc < t + 1;tc++) solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799;

int n, m, q;
int a[50], b[50], c[50], d[50];
int ans = 0;

void dfs(vector<int> seq){
  if(seq.size() == n){
    //得点計算
    int points = 0;
    for(int i = 0; i < q; i++){
      if(seq[b[i]-1] - seq[a[i]-1] == c[i]) points += d[i];
    }
    //cout << seq[0] << " "<<seq[1]<<" "<<seq[2]<<endl;
    ans = max(ans, points);
  }else{
    for(int i = seq.back(); i <= m; i++){
      //cout << seq[0] << " "<<seq[1]<<" "<<endl;
      seq.push_back(i);
      dfs(seq);
      seq.pop_back();
    }
  }
}
  

int main(){
  cin >> n >> m >> q;
  rep(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
  vector<int> v = {1};
  dfs(v);
  cout << ans<<endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
	ll a,b,c;
	cin>>a>>b>>c;
	int d=c,f=a;
	if(a>c){
		cout<<a-c<<" "<<b;
	return 0;
	}
	if(a==c){
		cout<<0<<" "<<b;
	return 0;
	}
	if(a<c){
		cout<<0<<" ";
	}
	c-=a;
	if(b>=c){
		cout<<b-c;
	return 0;
	}
	if(b<c){
		cout<<0;
	return 0;
	}
}	


Measured memory_bytes: 256
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double pi = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    map<int,int> meven;
    map<int,int> modd;
    int ceven = 0;
    int evenmax = 0;
    int evenmax2 = 0;
    int codd = 0;
    int oddmax = 0;
    int oddmax2 = 0;
    for(int i = 0; i < n; i++){
        if( i % 2 == 0){
            auto ite = meven.find(v[i]);
            if(ite != meven.end()){
                ite -> second = ite -> second + 1;
            }
            else{
                meven.insert(make_pair(v[i],1));
            }
        }
        else{
            auto ite = modd.find(v[i]);
            if(ite != modd.end()){
                ite -> second++;
            }
            else{
                modd.insert(make_pair(v[i],1));
            }
        }
    }
    for(auto ite = meven.begin(); ite != meven.end(); ++ite){
        int temp = ite -> second;
        if(evenmax < temp){
            evenmax = temp;
            ceven = ite -> first;
        }
    }
    for(auto ite = modd.begin(); ite != modd.end(); ++ite){
        if(oddmax < ite -> second){
            oddmax = ite -> second;
            codd = ite -> first;
        }
    }
    for(auto ite = meven.begin(); ite != meven.end(); ++ite){
        int temp = ite -> second;
        if(evenmax2 < temp && ceven != ite -> first){
            evenmax2 = temp;
        }
    }
    for(auto ite = modd.begin(); ite != modd.end(); ++ite){
        int temp = ite -> second;
        if(oddmax2 < temp && codd != ite -> first){
            oddmax2 = temp;
        }
    }
    if(codd != ceven) cout << (n / 2 - oddmax) + (n / 2 - evenmax) << endl;
    else cout << min((n / 2 - oddmax)+(n / 2 - evenmax2),(n / 2 - oddmax2)+(n / 2 - evenmax)) << endl;
    return 0;
}


Measured memory_bytes: 5376
#include <iostream>

using namespace std;
struct Node{
    int parent,left,right;
};

int main(){
    Node treeNode[100000];
    int n,id,k,c[100000],depth;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        treeNode[i].parent=treeNode[i].left=treeNode[i].right=-1;
    }
    for(int i=0;i<n;i++){
        cin>>id>>k;
        if(k>0){
            for(int j=0;j<k;j++)
            {
                cin>>c[j];
                treeNode[c[j]].parent=id;
            }
            for(int j=0;j<k-1;j++)
                treeNode[c[j]].right=c[j+1];
            treeNode[id].left=c[0];
        }
    }
    for(int i=0;i<n;i++)
    {
        depth=0;
        cout<<"node "<<i<<": "<<"parent = "<<treeNode[i].parent<<", depth = ";
        Node temp=treeNode[i];
        while(temp.parent!=-1)
        {
            depth++;
            temp=treeNode[temp.parent];
        }
        cout<<depth<<", ";
        if(treeNode[i].left==-1)
        {
            if(treeNode[i].parent!=-1)
                cout<<"leaf, []"<<endl;
            else
                cout<<"root, []"<<endl;
        }
        else
        {
            if(treeNode[i].parent!=-1)
                cout<<"internal node, ";
            else
                cout<<"root, ";
            temp=treeNode[treeNode[i].left];
            cout<<'['<<treeNode[i].left;
            while(temp.right!=-1){
                cout<<", "<<temp.right;
                temp=treeNode[temp.right];
            }
            cout<<']'<<endl;
        }
    }
}


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

vector<bool> furui_bool(int n) {
  vector<bool> fu(n + 1, 1);
  fu.at(0) = 0; fu.at(1) = 0;
  for (int i=2; i <= n/2 + 1; i++) {
    if (fu.at(i) == 1) {
      int j = 2 * i;
      while (j <= n) {
        fu.at(j) = 0;
        j += i;
      }
    }
  }
  return fu;
}

int main() {
  vector<bool> furui = furui_bool(100001);
  vector<int> a(100002,0),s(100002,0);
  for(int i=0;i<100002;i++){
    if(i%2==1 && furui[i] && furui[(i+1)/2]) a[i]++;
  }
  for(int i=0;i<100002;i++) s[i+1] = s[i]+a[i];
  int q,l,r;
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> l >> r;
    cout << s[r+1] - s[l] << endl;
  }
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin>>n;
  vector<ll> x(n),y(n);
  for(int i=0;i<n;i++){
    cin>>x[i];
    y[i]=x[i];
  }

  sort(y.begin(),y.end());
  map<ll,ll> mp;
  for(int i=0;i<n;i++){
    mp.insert(make_pair(y[i],i));
  }

  int index = (n+1)/2-1;
  vector<ll> b(n);
  for(int i=0;i<n;i++){
    int pl = mp[x[i]];
    if(pl > index) b[i] = y[index];
    else b[i] = y[index+1];
  }

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


Measured memory_bytes: 19072
N = (int(i) for i in input().split()) 
H = [int(i) for i in input().split()]

highest = 0
can_sea_hotels = 0

for i in range(len(H)):
    if highest <= H[i]:
        highest = H[i]
        can_sea_hotels += 1
    
print(can_sea_hotels)  

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
struct Scc {
	int n;
	vector<vector<int>> g,
		rg;//逆向きのグラフ
	vector<int> cmp,//cmp[i]:頂点iが属する強連結成分の番号
		visited,
		num;//帰りがけ順で頂点が入る
	Scc(int N) {
		n = N;
		cmp.resize(n);
		visited.resize(n);
		g.resize(n);
		rg.resize(n);
	}
	void add_edge(int from, int to) {
		g[from].push_back(to);
		rg[to].push_back(from);
	}

	void dfs(int v) {
		visited[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			if (!visited[g[v][i]])dfs(g[v][i]);
		}
		num.push_back(v);
	}

	void rdfs(int v, int k) {
		visited[v] = true;
		cmp[v] = k;
		for (int i = 0; i < rg[v].size(); ++i) {
			if (!visited[rg[v][i]])rdfs(rg[v][i], k);
		}
	}
	int calc() {
		for (int i = 0; i < n; ++i)visited[i] = false;
		num.clear();
		for (int i = 0; i < n; ++i) {
			if (!visited[i])dfs(i);
		}
		for (int i = 0; i < n; ++i)visited[i] = false;
		int k = 0;
		for (int i = num.size() - 1; i >= 0; --i) {
			if (!visited[num[i]]) {
				rdfs(num[i], k);
				++k;
			}
		}
		return k;
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vi d(n);
	REP(i, n)cin >> d[i];
	int mint = INF;
	REP(i, n) {
		mint = min(min(d[i], 24 - d[i]), mint);
	}
	RREP(t, mint + 1) {
		Scc scc(2 * n);
		int f = 1;
		REP(i, n) {
			FOR(j, i + 1, n) {
				if (abs(d[i] - d[j]) < t) {
					if (min(abs(d[i] + d[j] - 24), d[i] + d[j]) < t) {
						goto next;
					}
					else {
						scc.add_edge(n + j, i);
						scc.add_edge(i, n + j);
						scc.add_edge(n + i, j);
						scc.add_edge(j, n + i);

					}
				}
				if (min(abs(d[i] + d[j] - 24),d[i]+d[j]) < t) {
					scc.add_edge(i, j);
					scc.add_edge(j, i);
				}
			}
		}
		scc.calc();
		
		REP(i, n) {
			if (scc.cmp[i] == scc.cmp[n + i])f = 0;
		}
		if (f) {
			cout << t << endl;
			return 0;
		}
	next:;
	}
}


Measured memory_bytes: 384
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;


long comb(long n, long r) {
  vector<vector<long>> v(n + 1, vector<long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }

  return v[n][r];
}


long search(long num,long dig,long n,bool a3,bool a5,bool a7){
  long ans = 0;
  cerr <<num <<endl;
  if (num >n)return 0;

  ans += search(num+ 3 * pow(10,dig),dig+1,n,true,a5,a7);
  ans += search(num+ 5 * pow(10,dig),dig+1,n,a3,true,a7);
  ans += search(num+ 7 * pow(10,dig),dig+1,n,a3,a5,true);

  if (a3 && a5 &&a7){
    return ans + 1;
  }else{
    return ans;
  }

}



int main()
{
  int n, t; //かっている数//最大100
  long s;

  cin >> s;


  long ans = 0;


  ans = search(0,0,s,false,false,false);

  cout << ans;

  // cout << (mincost<10000000? to_string(mincost) :"TLE");

  return 0;
}



























Measured memory_bytes: 256