akhauriyash/Code-Regression huggingface dataset:
//  SMOKE SHISHA PLAY FIFA  // 
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define lp(start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	string s;
	cin >> s;
	ll ans=0;
	ll a=0;
	ll b=0;
	ll c=0;
	if(s[0]=='R')
		a=1;
	if(s[1]=='R')
		b=1;
	if(s[2]=='R')
		c=1;
	if(a&b&c)
	{
		cout << "3" << endl;
		return 0;
	}
	if((a+b+c)==0)
	{
		cout << "0" << endl;
		return 0;
	}
	else if((a+b+c)==1)
	{
		cout << "1" << endl;
		return 0;
	}
	else
	{
		if(a==1 && c==1)
		{
			cout << "1" << endl;
			return 0;
		}
		else
		{
			cout << "2" << endl;
			return 0;
		}
	}
	return 0;	
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
#define adrep(i,s,n) for (int i=(s);i<(n);i++)
using namespace std;
typedef long long ll;

int main(){
 
  string s,s2;
  cin>>s>>s2;
	
  string s3=s+s2;
  
  ll a;
  a=stol(s3);
  
  ll i=0;
  while(1){

    i++;
    
    if(i>sqrt(a))break;
    if(i*i==a){cout<<"Yes"<<endl;return 0;}
    
  }

  cout<<"No"<<endl;
  
    
}

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

using namespace std;

int main()
{
    int h, w, D;
    cin >> h >> w >> D;
    int a;
    int px[90001], py[90001];
    int d[90001];

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> a;
            px[a] = i;
            py[a] = j;
        }
    }

    for (int i = (D + 1); i <= h * w; i++)
    {
        d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D]);
    }
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << d[r] - d[l] << endl;
        // cout << "q:" << q << endl;
    }
    return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int mod = 1000000007;
long long dp[100005];;

long long gcd(long long a,long long b){

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

int main(){

 int n,m,x;
 int a[30] = {0};
 cin>>n>>m;

 for(int i=0;i<n;i++){
     cin>>x;
    for(int j=0;j<x;j++){
         int y;
       cin>>y;
       a[y-1]++;
    }
 }

  int cnt=0;
 for(int i=0;i<m;i++)
 {
    if(a[i] == n)
        cnt++;
 }

 cout<<cnt<<endl;

return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a=n/4+1;
    int b=n/7+1;
    for(int i=0;i<=a;i++)
    for(int j=0;j<=b;j++)
    {
        if(i*4+7*j==n)
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


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

//問題は、「中途半端に解く」か「解かない」か「完全に解く」の三パターン
int main(){
    int d, g, p[11], c[11]; //問題の種類の数、目標得点、問題数、コンプリートスコア
    cin >> d >> g; //dとgの入力
    for(int i = 0; i < d; ++i){ 
        cin >> p[i] >> c[i]; //pとcの入力
    }
 
    int ans = 1e9; //ans（解いた問題の最小値）の初期値を10^9に設定
    //maskのフラグが立っているのをコンプリートまたは中途半端に解く（１つだけ）とする
    for (int mask = 0; mask < (1 << d); ++mask){ //maskは0から2^d-1まで動く
        int total = 0; //総得点
        int proNum = 0; //解いた問題数
        int notSolve_max = -1; //解かない問題の最大番号
        for(int i = 0; i < d; ++i){ //i番目の問題について
            if (mask >> i & 1){ //maskのi番目のフラグが立っているなら
                total += 100 * (i+1) * p[i] + c[i]; //i番目の問題を全て解いた場合の点数を得点に追加
                proNum += p[i]; //解いた問題数にp[i]問追加
            }
            else { //i番目のフラグが立っていないなら
                notSolve_max = i; //解かない問題の最大値が何番目かを保存
            }
        }
        //以下、中途半端に解く問題について
        if (total < g){ //得点がg点よりも小さかったら
            int solvePoint_min = 100 * (notSolve_max + 1); //解かない問題の最大値の点数をsolvePoint_minとする
            int needNum = (g - total + solvePoint_min - 1) / solvePoint_min; //必要な残り問題数
            if (needNum >= p[notSolve_max]){ //必要問題数が存在する問題数に足りなかったら、このiは適していないので無視する
                continue; //次のループへ
            }
            proNum += needNum; //足りるなら、解いた問題数に必要問題数を足す
        }
        ans = min(ans, proNum); //ansとproNumの小さい方をansとする
    }
    cout << ans << endl; //ansを出力して
    return 0; //終了
}

Measured memory_bytes: 3604
input_ = [input() for i in range(4)]

N, K, X, Y = input_

acc = 0

if int(N) > int(K):
    acc = (int(K) * int(X)) + ((int(N) - int(K)) * int(Y))    
else:
    acc = int(N) * int(X)

print(acc)    

Measured memory_bytes: 3060
def main():
    n, x = map(int, input().split())
    a = [int(i) for i in input().split()]
    pref = [0, a[0]]
    for i in range(1, n): pref.append(a[i] + pref[i])
    ans = 0
    for val in pref:
        if val > x:
            break
        ans += 1
    print(ans)


main()


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

class num
{
public:
        int n;
};


int main()
{
 int a,b,m;
 cin >> a  >> b >> m;
 num A[a];
 num B[b];
 int A_min=1000000;
 int B_min=1000000;
 for(int i=0;i<a;i++){
     int v;
     cin >> v;
     A[i].n=v;
     if(v<A_min){
         A_min=v;
     }
 }
 for(int i=0;i<b;i++){
     int v;
     cin >> v;
     B[i].n=v;
     if(v<B_min){
         B_min=v;
     }
 }
 long ans=A_min+B_min;
 for(int i=0;i<m;i++){
     int x,y,c;
     cin >> x >> y >> c;
     x-=1;
     y-=1;
     long tmp=A[x].n+B[y].n-c;
     if(tmp<ans){
         ans=tmp;
     }
 }
 cout << ans;
 return 0;

}

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

public class Main {
    public static void main(String[] args) throws IOException {
        FastReader scan = new FastReader();
        //PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("marathon.out")));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        Task solver = new Task();
        //int t = scan.nextInt();
        int t = 1;
        for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
        out.close();
    }
    static class Task {
        public void solve(int testNumber, FastReader sc, PrintWriter pw) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            pw.println((n+m-1)/m);
        }
    }
    static class tup implements Comparable<tup>{
        int a, b;
        tup(int a, int b){
            this.a=a;
            this.b=b;
        }

        @Override
        public int compareTo(tup o) {
            return a!=o.a?Integer.compare(a,o.a):Integer.compare(b,o.b);
        }
    }
    static void shuffle(long[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            long temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

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

typedef pair<string,int>P;
int main(){
  int n,t;
  string names;
  int time,st=0;
  queue<P>que;
  cin>>n>>t;
  for(int i=0;i<n;i++){
    cin>>names>>time;
    que.push(P(names,time));
 }
  while(!que.empty()){
    P p=que.front(); que.pop();
    names=p.first;
    time=p.second;
    if(t<time){
      time-=t;
      st+=t;
      que.push(P(names,time));
    }
    else {
      st+=time;
      cout<<names<<" "<<st<<endl;
    } 
  }
}

Measured memory_bytes: 4404
A, B, C, D = map(int,input().split())
ans = "Yes"
curA = A
curC = C
for i in range(max(A,C)):
  curC  = curC-B
  if(curC<=0):
    ans = "Yes"
    break
  curA = curA-D
  if(curA<=0):
    ans = "No"
    break
print(ans)

Measured memory_bytes: 9192
#include <iostream>
#include <algorithm>

int calcMinimumPrice(int a, int b, int c, int x, int y) {
    int minPriceA = std::min(a, 2 * c);
    int minPriceB = std::min(b, 2 * c);
    int minPriceTwoAB = std::min(a + b, 2 * c);
    int z = std::min(x, y);
    return z * minPriceTwoAB + minPriceA * (x - z) + minPriceB * (y - z);
}

int main() {
    int a, b, c, x, y;
    std::cin >> a >> b >> c >> x >> y;
    std::cout << calcMinimumPrice(a, b, c, x, y) << std::endl;
}

Measured memory_bytes: 256
n = int(input())
init = int(pow(10, 9))
dp = [[init, init, init] for _ in range(n)]
dp[0] = list(map(int, input().split()))
for i in range(1, n):
    line = list(map(int, input().split()))
    dp[i][0] = line[0] + max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = line[1] + max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = line[2] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

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

using namespace std;

int main(void) {
    string S;
    cin >> S;
    if("00" < S.substr(0, 2) && S.substr(0, 2) < "13" && "00" < S.substr(2, 2) &&S.substr(2, 2) < "13") {
        cout << "AMBIGUOUS" << endl;
    } else if("00" < S.substr(0, 2) && S.substr(0, 2) < "13") {
        cout << "MMYY" << endl;
    } else if("00" < S.substr(2, 2) && S.substr(2, 2) < "13") {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String str;
		while ((str = reader.readLine()) != null) {
			int debt = 100000;
			int n = Integer.parseInt(str);
			for (int i = 0; i < n; i++) {
				debt *= 1.05;
				if (debt % 1000 != 0) {
					debt -= debt % 1000;
					debt += 1000;
				}
			}
			System.out.println(debt);
		}
		reader.close();
	}
}


Measured memory_bytes: 24144
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007
#define V 10

ll m[100][100];

int main() {
  ll h,w;
  cin>>h>>w;
  rep(i,0,V){
    rep(j,0,V){
      ll a;
      cin>>a;
      m[i][j] = a;
    }
  }
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (m[i][j] > m[i][k] + m[k][j]) {
          m[i][j] = m[i][k] + m[k][j];
        }
      }
    }
  }
  ll ans = 0;
  rep(i,0,h*w){
    ll a;
    cin>>a;
    if(a==-1)continue;
    ans += m[a][1];
  }
  cout << ans << endl;
  return 0;
}

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

#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define uniq(x) ((x).erase(unique(all(x)),(x).end()))
#define sz(x) ((int)(x).size())

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

string to_string(string s){
  return '"' + s + '"';
}
string to_string(const char *s){
  return to_string((string)s);
}
string to_string(bool b){
  return (b ? "true" : "false");
}
template<class A, class B>
string to_string(pair<A, B> p){
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C>
string to_string(tuple<A, B, C> p){
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> p){
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
template<class A>
string to_string(A v){
  bool first = true;
  string res = "{";
  for(const auto &x : v){
    if(!first){
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out(){cerr << endl;}
template<class Head, class... Tail>
void debug_out(Head H, Tail... T){
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL//compile with -DLOCAL
#define debug(...) cerr << "LINE" << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) void(0)
#endif

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

//区間変更・区間最大値取得
using S = long long;
using F = long long;
const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N,K;
  cin >> N >> K;

  vector<S> v(1e6, 0);
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
  rep(_,N){
    int a;
    cin >> a;
    int l = max(0,a-K);
    int r = min(int(1e6), a+K+1);
    int mx = seg.prod(l, r);
    seg.apply(a, a+1, mx+1);
  }
  cout << seg.prod(0, 1e6) << endl;

  return 0;
}

Measured memory_bytes: 35696
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;

/*
2>1>0
*/


struct D{
	ll a,t,x;
};
bool operator<(const D &l, const D &r){
	if(l.a < r.a){
		return true;
	}else if(l.a == r.a){
		if(l.t > r.t){
			return true;
		}else if(l.t == r.t){
			return l.x < r.x;
		}
	}
	return false;
}
ll n,q,s[200010],t[200010],x[200010],d[200010],ans[200010];
vector<D> a;
set<ll> st;

void init(){
	cin>>n>>q;
	rep(i,n)cin>>s[i]>>t[i]>>x[i];
	rep(i,q)cin>>d[i];
	rep(i,q)a.push_back({d[i],0,i});
	rep(i,n){
		a.push_back({s[i]-x[i],1,x[i]});
		a.push_back({t[i]-x[i],2,x[i]});
	}
	sort(a.begin(),a.end());
	// rep(i,a.size()){
	// 	printf("%lld,%lld,%lld\n",a[i].a,a[i].t,a[i].x);
	// }
}

int main(void){
	init();
	rep(i,a.size()){
		ll tmp=-1;
		if(!st.empty())tmp=*st.begin();
		if(a[i].t==0){
			ans[a[i].x]=tmp;
		}else if(a[i].t==1){
			st.insert(a[i].x);
		}else if(a[i].t==2){
			st.erase(a[i].x);
		}
	}
	rep(i,q){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 33124
s = list(input())
cnt0 = 0
cnt1 = 0

for i in range(len(s)):
    if i % 2 == 0:
        if s[i] == "1":
            cnt0 += 1
        else:
            cnt1 += 1
    else:
        if s[i] == "0":
            cnt0 += 1
        else:
            cnt1 += 1

print(min(cnt0, cnt1))

Measured memory_bytes: 3956
main = do 
    [a, b, c, d] <- map (read :: String -> Integer). words <$> getLine

    let d1 = div (a-1) c
    let d2 = div (a-1) d
    let d3 = div (a-1) (lcm c d)
    let d4 = div b c
    let d5 = div b d
    let d6 = div b (lcm c d)

    print $ b - a + 1 - ((d4 + d5 - d6) - (d1 + d2 - d3))



Measured memory_bytes: 508
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <random>
#include <fstream>
#include <time.h>
#define int long long
#define debug(x) cerr << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1000000007;
const ll LINF = 1e18;
const double EPS = 1e-9;


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

  char b;
  cin>>b;
  char ans;
  if(b == 'A') {
    ans = 'T';
  } else if (b == 'T') {
    ans = 'A';
  } else if (b == 'C') {
    ans = 'G';
  } else if (b == 'G') {
    ans = 'C';
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m, ans=0; 
    cin >> n >> m;
    vector<int> x(m),y(m-1);
    for(int i=0; i<m; i++) cin >> x[i];
    sort(x.begin(), x.end());
    if(n<m) {
        for(int i=0; i<m-1; i++) y[i]=x[i+1]-x[i];
        sort(y.begin(), y.end());
        for(int i=0; i<m-n; i++) ans += y[i];
    }
    cout << ans;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS  head
#include <cstdio>  
#include <cstring>  
#include <queue>
#include <algorithm>  
using namespace std;
const int N = 1e5 + 7;
int n, tot; //树的根节点  
int head[N]; //存的边的信息，head_cpy[i]表示第i个节点的头指针  
struct Edge {
	int to, w, nxt;
}edge[N << 1]; 
bool vis[N];
void init() {
	tot = 0;
	memset(head, -1, sizeof head);
	memset(vis, 0, sizeof vis);
}
void add(int u, int v, int w) {
	edge[tot].to = v;
	edge[tot].w = w;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}
long long dis[N]; 
void bfs(int rt) {
	queue<int> q;
	q.push(rt);
	vis[rt] = 1;
	dis[rt] = 0;
	while (!q.empty()) {
		rt = q.front(); q.pop();
		for (int i = head[rt]; ~i; i = edge[i].nxt) {
			int v = edge[i].to;
			if (!vis[v]) {
				vis[v] = true;
				dis[v] = dis[rt] + edge[i].w;
				q.push(v);
			}
		}
	}
}
int main()
{
	while (~scanf("%d", &n)) {
		init();
		int u, v, w;
		for (int i = 1; i < n; ++i) { //读入n-1条边  
			scanf("%d%d%d", &u, &v, &w);
			add(u, v, w);
			add(v, u, w);
		}
		int m, k, x, y;
		scanf("%d%d", &m, &k);
		bfs(k);
		//for (int i = 1; i <= n; ++i) printf("%lld%c", dis[i], " \n"[i==n]);
		while (m--) {
			scanf("%d%d", &x, &y);
			long long len = 0;
			len = dis[x] + dis[y];
			printf("%lld\n", len);
		}
	}

	return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long
//typedef pair<int, int> P;
//typedef tuple<string, int, int> T;

int N, T;
int A[100100];

signed main() {
    cin >> N >> T;
    rep(i, N) cin >> A[i];
    map<int, int> cnt;
    int m = 10000000000;
    int maxp = 0;
    rep(i, N) {
        m = min(m, A[i]);
        maxp = max(maxp, A[i]-m);
        cnt[A[i]-m]++;
    }
    cout << cnt[maxp] << endl;
}

Measured memory_bytes: 7296
#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

ll n, k;
vll limit;

vvll no_of_ways, sum_no_of_ways;

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;
    
    limit.resize(n+1);
    no_of_ways.resize(n+1, vll(k+1));
    sum_no_of_ways.resize(n+1, vll(k+1));

    for(ll i = 1; i <= n; ++i) cin >> limit[i];

    no_of_ways[0][0] = 1;
    for(ll i = 1; i <= k; ++i) no_of_ways[0][k] = 0;

    for(ll i = 1; i <= n; ++i){
        sum_no_of_ways[i-1][0] = no_of_ways[i-1][0];
        for(ll j = 1; j <= k; ++j)
            sum_no_of_ways[i-1][j] = (sum_no_of_ways[i-1][j-1] + no_of_ways[i-1][j])%MOD;
        for(ll j = 0; j <= k; ++j){
            ll left = j, right = (j - limit[i] - 1);
            no_of_ways[i][j] = sum_no_of_ways[i-1][left];
            if(right >= 0)
                no_of_ways[i][j] = (no_of_ways[i][j] - sum_no_of_ways[i-1][right]+MOD)%MOD;
        }
    }

    cout << no_of_ways[n][k] << endl;

    return 0;
}

//cikisir



Measured memory_bytes: 159088
#include <iostream>
#include <limits.h> 
using namespace std;

int main(void){
	int N, *A, dif, max, minID, maxID;

	cin >> N;

	A = new int[N];
	maxID = 1;
	minID = 0;

	for (int i = 0; i < 2; i++){
		cin >> A[i];
	}

	max = A[maxID] - A[minID];
	if (A[maxID] < A[minID]){
		minID = 1;
	}

	for (int i = 2; i < N; i++){
		cin >> A[i];		

		if (minID > maxID || A[maxID] < A[i]){
			maxID = i;
			if (max < A[maxID] - A[minID] && maxID > minID) max = A[maxID] - A[minID];
		}
		if (A[minID] > A[i]){
			minID = i;
		}
	}

	cout << max << "\n";

	return 0;
}

Measured memory_bytes: 1968
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<LL,LL>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    LL from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
class UnionFind{
private:
    vector<int> vec;
public:
    void init(int N){
        vec.resize(N);
        for(int a = 0;a < N;a++)
        {
            vec[a]=-1;
        }
    }
    int root(int a)
    {
        if(vec[a] < 0)return a;
        else return vec[a] = root(vec[a]);
    }
    bool connect(int a,int b)
    {
        a = root(a);
        b = root(b);
        if(a==b)return false;
        if(vec[a] > vec[b])swap(a,b);
        vec[a] += vec[b];
        vec[b] = a;
        return true;
    }
    bool check(int a,int b){
        a = root(a);
        b = root(b);
        if(a==b)return true;
        else return false;
    }
};
bool comp(const Edge& e1, const Edge& e2){
    return e1.value < e2.value;
}
LL kruskal(V<Edge> Edges,int N){
    sort(ALL(Edges), comp);
    UnionFind Uni;
    Uni.init(N);
    LL ans = 0;
    for(int a = 0;a < Edges.size();a++){
        Edge e = Edges.at(a);
        if(!Uni.check(e.from,e.to)){
            Uni.connect(e.from,e.to);
            ans += e.value;
        }
    }
    return ans;
}
int main(){
    CIN(N);
    V<Edge> vec;
    V<pair<LL,LL>> q;
    V<pair<LL,LL>> p;
    REP(a,N){
        LCIN(b);
        LCIN(c);
        q.pb(make_pair(b,a));
        p.pb(make_pair(c,a));
    }
    sort(ALL(p));
    sort(ALL(q));
    for(int a = 0;a < N-1;a++){
        Edge e(p.at(a).second,p.at(a+1).second,abs(p.at(a).first-p.at(a+1).first));
        Edge w(q.at(a).second,q.at(a+1).second,abs(q.at(a).first-q.at(a+1).first));
        vec.pb(e);
        vec.pb(w);
    }
    COUT(kruskal(vec,N));
    return 0;
}


Measured memory_bytes: 15708
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>

using namespace std;
int main() {
    int N;
    cin >> N;
    if(N < 1000) {
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }
}

Measured memory_bytes: 256
// defines
#define boost_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define casti static_cast<int>
#define cast static_cast
#define ll long long int
#define vi vector<int>
#define vpi vector<pair<int,int >>

// includes
#include <bits/stdc++.h>

using namespace std;

ll modF=1e9+7;

// topcoder


//codechef and codeforces

void solve1(){
    int n;
    cin>>n;
    int inp;
    map<int,int> a;
    int maxv=0;
    for(int i=0;i<n;i++){
        cin>>inp;
        if(inp>maxv)
            maxv=inp;
        if(a.find(inp)==a.end()){
            a[inp]=1;
        }
        else{
            a[inp]++;
        }
    }
    vector<bool> h(maxv+1,true);
    for(int i=1;i<=maxv;i++){
        map<int,int>::iterator it1;
        if((it1=a.find(i))!=a.end()){
            if(it1->second>1)
                h[i]=false;
            for(int j=2*i;j<=maxv;j+=i){
                    h[j]=false;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=maxv;i++){
        if(h[i]){
            if(a.find(i)!=a.end()){
                ans++;
            }
        }
    }
    cout<<ans<<"\n";
}

int main(){
    boost_io;
    solve1();
    return 0;
}


Measured memory_bytes: 13032
//
// Created by yamunaku on 2020/01/10.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int k, x;
    cin >> k >> x;
    if(500 * k >= x) CYES;
    else
        CNO;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        String N = sc.next();
        System.out.println(solve(N));

        /*
        int[] ans = {
                0, 1, 2, 3 ,4, 5, 5, 4, 3, 2,
                1, 2, 3, 4, 5, 6, 6, 5, 4, 3,
                2, 3, 4, 5, 6, 7, 7, 6, 5, 4,
                3, 4, 5, 6, 7, 8, 8, 7, 6, 5,
                4, 5, 6, 7, 8, 9, 9, 8, 7, 6,
                5, 6, 7, 8, 9, 10, 9, 8, 7, 6,
                5, 6, 7, 8, 9, 9, 8, 7, 6, 5,
                4, 5, 6, 7, 8, 8, 7, 6, 5, 4,
                3, 4, 5, 6, 7, 7, 6, 5, 4, 3,
                2, 3, 4, 5, 6, 6, 5, 4, 3, 2,
                1
        };
        for (int i=0; i<ans.length; i++) {
            if (solve(String.valueOf(i)) != ans[i]) {
                System.err.println("fail: " + i + " -> " + solve(String.valueOf(i)) + " but expect " + ans[i]);
            }
        }
         */

    }

    private static long solve(String N) {
        long count = 0;

        int[] convert = {
                0, 1, 2, 3 ,4, 5, 4, 3, 2, 1
        };

        int keta = 0;
        for (int i=0; i<N.length(); i++) {
            int val = N.charAt(N.length()-i-1) - '0';

            if (val+keta == 5 && i != N.length()-1) {
                int nextVal = N.charAt(N.length()-i-2) - '0';
                if (nextVal >= 5) {
                    keta = 1;
                    count += 5;

                    continue;
                }
            }

            count += convert[(val+keta)%10];
            if (val+keta >= 6) {
                keta = 1;
            } else {
                keta = 0;
            }
            // System.err.println("val=" + val + ", keta=" + keta + ", count=" + count);
        }
        if (keta == 1) {
            count += 1;
        }

        return count;
    }
}

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

int main(){
    for(int i = 0; ;i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1){
            break;
        }
        if(a == -1 || b == -1){
            cout << "F" << endl;
            continue;
        }

        if(a+b >= 80){
            cout << "A" << endl;
            continue;
        }else if (a+b < 80 && a+b >= 65){
            cout << "B" << endl;
            continue;
        }else if ((a+b>=50 && a+b < 65)){
            cout << "C" << endl;
            continue;
        }else if (a+b >= 30 && a+b < 50){
            if(c >= 50){
                cout << "C" << endl;
                continue;
            }else{
                cout << "D" << endl;
                continue;
            }
        }else{
            cout << "F" << endl;
            continue;
        }
    }
    return 0;
}


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

int main() {
  string s;
  cin>>s;
  int z=0,o=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='0'){
      z++;
    }
    else{
      o++;
    }
  }
  cout<<min(z,o)*2;
}


Measured memory_bytes: 512
vs = input().split()

stack = []
for v in vs:
    if v == '+':
        stack.append(stack.pop() + stack.pop())
    elif v == '-':
        stack.append(-stack.pop() + stack.pop())
    elif v == '*':
        stack.append(stack.pop() * stack.pop())
    else:
        stack.append(int(v))

print(stack.pop())



Measured memory_bytes: 5596
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int dp[2][1000006];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, W;
  cin >> N >> W;
  int v[N], w[N];
  FOR(i,0,N) cin >> v[i] >> w[i];
  FOR(i,0,N){
    FOR(j,0,W+1) {
      // 入れる
      if(j+w[i] <= W) dp[(i+1)%2][j+w[i]] = max(dp[(i+1)%2][j+w[i]], dp[i%2][j] + v[i]);
      // 入れない
      dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);
    }
    FOR(j,0,W+1) {
      dp[i%2][j] = dp[(i+1)%2][j];
    }
  }
  int ans = 0;
  FOR(i,0,W+1) ans = max(ans, dp[N%2][i]);
  cout << ans << endl;
}


Measured memory_bytes: 3280
using System;
using System.Linq;

namespace AtCoder
{
	class Program
	{
		public static void Main()
		{
			var length = IO.ReadInt();
			var chars = IO.ReadCharArray();
			var lengths = new long[]
			{
				chars.Count(iChar => iChar == 'R'),
				chars.Count(iChar => iChar == 'G'),
				chars.Count(iChar => iChar == 'B')
			};

			var combiNum = lengths.Aggregate((iCurrent , iNext) => iCurrent * iNext);
			for(var iIndex0 = 0 ; iIndex0 < length ; ++ iIndex0)
			{
				for(var iIndex1 = iIndex0 + 1 ; iIndex1 < length ; ++ iIndex1)
				{
					if(chars[iIndex0] == chars[iIndex1]) { continue; }

					var lastIndex = (iIndex1 * 2) - iIndex0;
					if(lastIndex < length && 
					   chars[iIndex0] != chars[lastIndex] &&
					   chars[iIndex1] != chars[lastIndex])
					{
						-- combiNum;
					}
				}
			}
			IO.Write(combiNum);
		}
	}

	public static class IO
	{
		public static string   Read()							  { return Console.ReadLine(); }
		public static string[] ReadArray(char iSplitter = ' ')	  { return Read().Split(iSplitter); }
		public static int	   ReadInt()						  { return int.Parse(Read()); }
		public static int[]	   ReadIntArray(char iSplitter = ' ') { return ReadArray().Select(iText => int.Parse(iText)).ToArray(); }
		public static char[]   ReadCharArray()					  { return Read().ToCharArray(); }

		public static void Write(string iValue)  { Console.WriteLine(iValue); }
		public static void Write(int iValue)	 { Console.WriteLine(iValue); }
		public static void Write(long iValue)	 { Console.WriteLine(iValue); }
		public static void Write(decimal iValue) { Console.WriteLine(iValue); }
		public static void Write(bool iValue)	 { Console.WriteLine(iValue ? "Yes" : "No"); }
	}

	public static class Util
	{
		public static long Gcd(long i0 , long i1)	{ return (i0 > i1) ? _Gcd(i0 , i1) : _Gcd(i0 , i1); }
		private static long _Gcd(long i0 , long i1)	{ return (i1 == 0) ? i0 : _Gcd(i1 , i0 % i1); }
	}
}


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

using namespace std;

int main () {

  int A, B;
  cin >> A >> B;

  int max = (A + A - 1 >= B + B - 1) ? A + A - 1 : B + B - 1;

  if (max < A + B) {
    max = A + B;
  }

  cout << max << endl;

  return 0;
}

Measured memory_bytes: 256
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n =INT()

dd = defaultdict(int)

for _ in range(n):
    dd[input()]+=1

mx = max(dd.values())
zz=  []
for k in dd:
    if(dd[k]==mx):
        zz.append(k)
zz.sort()
# print(zz)
for _ in range(len(zz)):
    print(zz[_])

Measured memory_bytes: 147004
#include <stdio.h>
#include <string.h>

int main(void)
{
	int n,i;
  scanf("%d",&n);
	char str1[n];
	
	scanf("%s",str1);
	if(n%2==1){
printf("No\n");
    }else{
	for (i = 0;i < n/2 + 1;i++) {
		if (str1[i] != str1[i+n/2]) break;
	}
	
	if (i ==n/2 ) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
    }
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<math.h>
int main(){
	int N,a[10000],b[10000],i,j,k,l=1,sum=0;
	b[0]=2;b[1]=3;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&a[i]);}
	for(i=0;i<N;i++){
		k=1;
		if(a[i]==0){k=0;}
		if(a[i]==1||a[i]==2||a[i]==3){sum++;k=0;}
		if(k){for(j=0;j<l;j++){
			if(a[i]%b[j]==0)k=0;}}		
		if(k){
			for(j=2;j<=sqrt((double)a[i]);j++){
				if(a[i]%j==0)k=0;}}
		if(k){sum++;l++;b[l]=a[i];}}
	printf("%d\n",sum);
	return 0;}


Measured memory_bytes: 2772
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,s=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y)
		{
			s++;
			if(s==3)
			{
				puts("Yes");
				return 0;
			}
		}
		else
			s=0;
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repi(i,a,b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  
 cout << (abs(x-a) < abs(x-b) ? "A" : "B") << endl;
}

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

int main(){
    int N;  cin >> N;
    vector<vector<ll>> A(N, vector<ll>(N, 0));
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        cin >> A[i][j];
    }

    vector<vector<ll>> dist = A;
    for(int i=0; i<N; i++) dist[i][i] = 0;
    for(int k=0; k<N; k++) for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
    }

    ll ans = 0;
    for(int u=0; u<N; u++) for(int v=u+1; v<N; v++){
        ll d = 1e18;
        for(int k=0; k<N; k++){
            if(k==u || k==v) continue;
            d = min(d, dist[u][k] + dist[k][v]);
        }
        if(d < A[u][v]){
            cout << -1 << endl;
            return 0;
        }else if(d > A[u][v]){
            ans += A[u][v];
        }
    }
    cout << ans << endl;
}


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

int main() {
  string S; cin >> S;
  int i = S.size();
  string T[4] = {"dream","dreamer","erase","eraser"};
  while (i > 0) {
    int previ = i;
    for (int j = 0; j < 4; j++) {
      if (T[j] == S.substr(max(0, i - (int)T[j].size()), T[j].size())) i = i - T[j].size();
      if (i == 0) break;
    }
    if (i == previ) break;
  }
  if (i == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







vector<vector<ll>> g;
vector<ll> d;
ll ans = 0;

void dfs1(ll now, ll par, ll dist){
    d[now] = dist;
    for(auto &c : g[now]){
        if(c == par) continue;
        dfs1(c, now, dist + 1);
    }
}

void dfs2(ll now, ll par, ll dist){
    ans = max(ans, d[now] - 1);
    if(d[now] <= dist) return;
    for(auto &c : g[now]){
        if(c == par) continue;
        dfs2(c, now, dist + 1);
    }
}


int main(){
    ll n, u, v;
    cin >> n >> u >> v;
    u--; v--;
    g.resize(n);
    d.resize(n);
    REP(i, n - 1){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(v, -1, 0);
    dfs2(u, -1, 0);
    cout << ans << endl;
}

Measured memory_bytes: 11520
(function(stdin){
	var lines = stdin.toString().split('\n'); 
    var param = lines[0].split(' ').map(Number);
    var a  = param[0];
    var b  = param[1];
  console.log([a * b,a*2+b*2].join(' '));
}(require('fs').readFileSync('/dev/stdin','utf8')));

Measured memory_bytes: 7384
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define NDEBUG
#define debug(...)
#define IFD(...)
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <cassert>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <iostream>
#include <iomanip>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = static_cast<int>(a); i <= static_cast<int>(b); ++i)
#define FORD(i, b, a) for (int i = static_cast<int>(b); i >= static_cast<int>(a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int n;
    i64 w;
    cin >> n >> w;
    vector w_s(n, 0);
    vector<i64> v_s(n);
    rep(i, n)
    {
        cin >> w_s[i] >> v_s[i];
    }

    // [0,i)の品物を使った重さj以下の解
    vector dp(n + 1, vector<i64>(w + 1));
    rep(i, n)
    {
        dp[i + 1] = dp[i];
        rep(j, w + 1 - w_s[i])
        {
            chmax(dp[i + 1][j + w_s[i]], dp[i][j] + v_s[i]);
        }
    }
    debug(dp);
    cout << dp[n][w] << '\n';

    return 0;
}


Measured memory_bytes: 83168
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

if L[0] != 0 or any(l == 0 for l in L[1:]):
    print(0)
    exit()

C = Counter(L)
MOD = 998244353
ans = 1
for i, j in enumerate(range(1, max(L)+1)):
    prev = C[i]
    cur = C[j]
    ans *= prev**cur
    ans %= MOD
print(ans)


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const lb PI=3.14159265359;

int main(){

  ll n;cin>>n;

  ll ans=0;
  repr(i,n,1){
    ll count=0;
    if(i%2==0)continue;
    repr(j,i,1){
      if(i%j==0)count++;
    }
    if(count==8)ans++;
  }

  out(ans);

  return 0;
}


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

int main() {
 string s;cin >> s;
  int n=s.size();
  int cnt=0,ans;
  bool ok=false;
  for(int i=n-2;i>0;i=i-2){
   int m=i/2;
    for(int j=0;j<m;j++){
      if(s[j]==s[j+m])cnt++;
    }
    if(cnt==m){
    ans=i;
    break;
    }
    cnt=0;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int X, a, b;
 
int main (){
	cin >> X >> a >> b;
	
	if(a+X<b) cout << b-(a+X) << endl;
	else if(b+X<a) cout << a-(b+X) << endl;
	else cout << 0 << endl;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<bool>isAc(n,false);
    vector<int>penaltyV(n,0);
    for(int i = 0; i < m; i++){
        int p = 0;
        string s = "";
        cin >> p >> s;
        p--;
        if(s.compare("AC")==0){
            isAc[p]=true;
        }else{
            if(isAc[p]==false){
                penaltyV[p]++;
            }
        }
    }
    long acNum = 0;
    long penalty = 0;
    for(int i = 0; i < n; i++){
        if(isAc[i]==true){
            acNum++;
            penalty += penaltyV[i];
        }
    }
    cout << acNum << " " << penalty << endl;;
    return 0;
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
#define LINF 1e18
typedef long long ll;


int main() {

    int N,M; cin >> N >> M;
    dsu d(N);
    REP(i,M){
        int a,b; cin >> a >> b;
        a--;
        b--;
        d.merge(a,b);
    }
    cout << d.groups().size()-1 << endl;
    return 0;
}

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

int main() {
int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c) cout << 1 << endl;
   if (a == b && b != c || a == c && c != b || b == c && c != a) cout << 2 << endl;
  if ( a != b && b != c && c != a) cout << 3 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
using namespace std;
using ll = long long;

int main() {
    ll n,m,d;cin>>n>>m>>d;
    double half;
    if (d==0) half = n;
    else half = 2 * (n - d);
    double ans = (double)(half) * (double)(m -1) / (double)(n * n);
    cout << setprecision(9) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

int min(int a,int b){
	return (a>b)?b:a;
}

int main(){
	long long w,h,in;
	cin>>w>>h;
	pair<ll,bool> p[w+h];
	rep(i,w+h){
		cin>>in;
		if(i<w)p[i]=pair<ll,bool>(in,false);
		else p[i]=pair<ll,bool>(in,true);
	}
	sort(p,p+w+h);
	long long x=0,y=0,ans=0;
	rep(i,w+h){
		ans+=p[i].first*((p[i].second)?(w+1-x):(h+1-y));
		if(p[i].second)y++;
		else x++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string S;
    cin >> S;
    if(S == "Sunny"){
        cout << "Cloudy" << endl;
    }
    else if(S == "Cloudy"){
        cout << "Rainy" << endl;
    }
    else if(S == "Rainy"){
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>

using namespace std;
using ll=long long int;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &e: a) cin >> e;

    double d = 0;
    for (int i = 0; i < n; ++i) {
        d += 1.0/a[i];
    }
    cout << fixed << setprecision(20) << 1.0/d << endl;

    return 0;
}


Measured memory_bytes: 256