akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long lol;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(lol i=0;i<lol(n);i++)
#define REPD(i,n) for(lol i=n-1;i>=0;i--)
#define FOR(i,a,b) for(lol i=a;i<=lol(b);i++)
#define FORD(i,a,b) for(lol i=a;i>=lol(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) lol(x.size()) //sizeをsize_tからllに直しておく
//定数
#define PI 3.1415926535897932385 //pi
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//最大値最小値
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main()
{
    lol result{0};
    lol k; cin >> k;
    if(k%2 == 0 || k%5 == 0)
    {
        result = -1;
    }
    else
    {
        lol l;
        if(k%7 == 0)
            l = 9*k/7;
        else
        {
            l = 9*k;
        }
        lol re{1};
        while(true)
        {
            re = (10*re)%l;
            result++;
            //cout << re << endl;
            if(re == 1)
                break;
        }
    }
    

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3584
n, q = map(int, input().split())
s = input()
l = []
r = []
t = [0]*len(s)

for i in range(q):
    temp1, temp2 = map(int, input().split())
    l.append(temp1)
    r.append(temp2)

for i in range(1, len(s)):
    if s[i-1] + s[i] == 'AC':
        t[i] = t[i-1] + 1
    else:
        t[i] = t[i-1]

#print(t)

for i in range(q):
    left = l[i] - 1
    right = r[i] - 1
    # print(left)
    # print(right)
    print(t[right] - t[left])

Measured memory_bytes: 14200
n=int(input())

a=list(map(int,input().split()))
q=int(input())
l=[list(map(int,input().split())) for i in range(q)]

import collections
c = collections.Counter(a)

m=sum(a)
for i in range(q):
    m+=c[l[i][0]]*(l[i][1]-l[i][0])
    print(m)

    b=c[l[i][0]]
    c[l[i][0]]=0
    c[l[i][1]]+=b


Measured memory_bytes: 104660
N,M = map(int,input().split())
C = {i:[0,1] for i in range(1,N+1)}
C[1] = [1,1]
for _ in range(M):
    x,y = map(int,input().split())
    if C[x][0]==1:
        C[y][0]=1
    C[y][1] += 1
    C[x][1] -= 1
    if C[x][1]==0:
        C[x][0]=0
cnt = 0
for i in range(1,N+1):
    if C[i][0]==1:
        cnt += 1
print(cnt)

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

int main(){
  int64_t N, P;
  cin >> N >> P;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  int64_t ans = 0;
  int even = 0;
  for(int j=0; j<N; j++){
    if(vec.at(j) %2 == 0){
      even++;
    }
  }
  if(even == N){
    if(P == 0){
    ans = pow(2,N);
    }
    else{
      ans = 0;
    }
  }
  else{
    ans = pow(2, N-1);
  }
  cout << ans << endl;
} 

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

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

    int ans = 0;

    for (int i = 0; i < 3; ++i) {
        if (S[i] == T[i]) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int a[100],n;
	do{
		scanf("%d",&n);
		printf("");
	}while(!(n>=0 && n<=100));
	int t;
	for(t=0;t<n;t++){
		scanf("%d ",&a[t]);
	}
	for(t=n-1;t>=0;t--){
		if(t==0){
			printf("%d",a[t]);
		}else{
			printf("%d ",a[t]);
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 604
/*
I believe on myself and I will achieve
this->author = Fuad Ashraful Mehmet, CSE ,University of Asia Pacific
Todo:
https://codeforces.com/problemset/problem/830/B
*/
#include<bits/stdc++.h>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define all(o) (o).begin(),(o).end()
#define dbg(o)  cerr<<"at "<<__LINE__<<" response = "<<o<<endl;
#define pb push_back
using namespace std;

typedef long long ll;
const int N=1e5+5;
int q,k,m,n,cs=1;

void HalfDead()
{
	string s;
	cin>>s;
	int len=(int)s.size();
	cout<<s;
	s[len-1]=='s'?cout<<"es":cout<<"s";
	cout<<endl;
}
int main()
{
      ios_base::sync_with_stdio(0); cin.tie(nullptr);  cout.tie(0);
      // cout<<setprecision(10)<<fixed;
      int tc=1;
     // cin>>tc;
      while(tc--)
      {   
          HalfDead();
      }
      return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main() {
  ll n, k;
  cin >> n >> k;

  long double ans = 0;
  for (ll i = 1; i <= n; ++i) {
    if (i >= k) {
      ans += 1.0 / double(n);
    } else {
      ll x = 1;
      for (; ; ++x) {
        if ((i<<x) >= k) break;
      }
      //cout << "1.0/" << double(n) << " + " << "1.0/" << (2<<(x-1)) << " : i=" << i << " x=" << x <<  endl;
      ans += 1.0 / double(n) * 1.0/(2<<(x-1));
    }
  }

  cout << fixed << setprecision(10);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt(),x=sc.nextInt();
		int[] a = new int[m];
		for(int i=0; i<m; i++) {
			a[i]=sc.nextInt();
		}
		int cost1=0,cost2=0;
		for (Integer i : a) {
			if(i > x) cost1++;
			if(i < x) cost2++;
		}
		System.out.println(cost1 < cost2 ? cost1:cost2);
	}
}


Measured memory_bytes: 21972
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] >= 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Measured memory_bytes: 66244
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} 

//最長単調増加連速部分数列
int LmonoIS(const VI &X){
    int mlen = 0, len = 1;
    rep(i, 0, X.size()-1){
        if (X[i] < X[i+1]) ++len;
        else {
            mlen = max(mlen, len);
            len = 1;
        }
    }
    return max(mlen, len);
}

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

int N; cin >> N;
VI X(N);
rep(i, 1, N+1){
    int p; cin >> p;
    X[p-1] = i;
}

cout << N - LmonoIS(X) << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 1792
a = list(str(input()))
b = list(set(a))
c = len(b)
c_ = []

if c == 1:
    print(0)
else:
    for i in b: 
        count = 0
        a_ = a[:]
        while len(list(set(a_)))!=1:
            for j in range((len(a_)-1)):
                if a_[(1+j)] == i:
                    a_[j] = i
            del a_[-1]
            count+=1
        c_.append(count)
    c_.sort()
    print(c_[0])

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

int gcd(int a,int b){
  int temp;
  while(b!=0){
    temp=a%b;
    a=b;
    b=temp;
  }
  return a;
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  bool pc=true;
  vector<bool> d(1e6+1,false);
  int n,a;
  for(int i=0;i<N;i++){
    if(A.at(i)==1){
      continue;
    }
    if(d.at(A.at(i))){
      pc=false;
      break;
    }
    n=A.at(i);
    a=2;
    while(a*a<=n){
      if(n%a==0){
        n/=a;
        if(!d.at(a)){
          for(int j=a;j<d.size();j+=a){
            d.at(j)=true;
          }
        }
      }else{
        a++;
      }
    }
    if(!d.at(n)){
      for(int j=n;j<d.size();j+=n){
        d.at(j)=true;
      }
    }
    if(!pc){
      break;
    }
  }
  if(pc){
    cout << "pairwise coprime" << endl;
    return 0;
  }
  int g=gcd(A.at(0),A.at(1));
  for(int i=2;i<N;i++){
    g=gcd(A.at(i),g);
  }
  if(g!=1){
    cout << "not coprime" << endl;
  }else{
    cout << "setwise coprime" << endl;
  }
  return 0;
}


Measured memory_bytes: 7184
import sys
lines = [s.rstrip("\n") for s in sys.stdin.readlines()]
n, = [int(num) for num in lines.pop(0).split(" ")]
words = lines
prev_last_char = None
words_already_used = {}
for w in words:
    if w in words_already_used:
        print("No")
        break
    else:
        words_already_used[w] = True
    if prev_last_char is not None:
        if w[0] != prev_last_char:
            print("No")
            break
    prev_last_char = w[-1]
else:
    print("Yes")


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

#define N 200010
#define MAX 1000000000000000000

#include <stdio.h>

int main (void) {
    int n;

    scanf("%d", &n);

    if (n % 1000 == 0) {
        puts("0");
    } else {
        printf("%d", 1000 - (n % 1000));
    }

    return 0;

}



Measured memory_bytes: 1732
N,M=map(int,input().split())
keep=[]
lis=[]
ac=[0]*N
wa=[0]*N
WA=0
for i in range(M):
    ps=input().split()
    keep.append(ps)
    
for j in range(M):
    if keep[j][1]=="AC":
        ac[int(keep[j][0])-1]=1
    elif ac[int(keep[j][0])-1]==0:
        wa[int(keep[j][0])-1]+=1
AC=sum(ac)
for k in range(N):
    WA+=ac[k]*wa[k]
    
print(AC,WA)


Measured memory_bytes: 33684
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll k[50][30];
ll p[26];
int main(){
  ll n;
  cin>> n;
  string s[n];
  for(ll i=0;i<n;i++) {
    cin >>s[i];
    sort(s[i].begin(),s[i].end());
    ll ss=s[i].size();
    for(ll j=0;j<ss;j++) k[i][s[i][j]-'0'-49]++;
  }
  for(ll i=0;i<26;i++){
    ll mi=100;
    for(ll j=0;j<n;j++){
      mi=min(k[j][i],mi);
    }
    p[i]=mi;
    
  }
  for(ll i=0;i<26;i++){
    string l;
    l+='a'+i;
    for(ll j=0;j<p[i];j++) cout <<l;
  }
  cout <<endl;
}


Measured memory_bytes: 256
def solve(a, b, c):

    def gcd(a, b):
        if a > b:
            a, b = b, a
        while a % b != 0:
            a, b = b, a % b
        return b

    return 'YES' if c % gcd(a, b) == 0 else 'NO'

_a, _b, _c = list(map(int, input().split()))
print(solve(_a, _b, _c))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)


//dp[i][j] = 数列の区間 [i, j) に対して操作を施せる回数の最大値
int main() {
    int n;
    while(cin >> n){       
        if(n==0) break;
        vector<int> w(n);
        rep(i,n) cin >> w[i];
        vector<vector<int> > dp(n+1, vector<int>(n+1, -n));
        rep(i,n+1) {
            dp[i][i] = 0;
            if(i < n) dp[i][i+1] = 0;
        }
        for(int length = 2;  length <= n; ++length){
            for(int i = 0; i+ length<=n; ++i){
                int j = i + length;
                if(dp[i+1][j-1]==j-i-2){
                    if(abs(w[i]-w[j-1])<=1) dp[i][j] = max(dp[i][j], j-i);
                    else dp[i][j] = max(dp[i][j], j-i-2);
                }
                for(int k = i+1; k <= j-1; ++k){
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        cout << dp[0][n] << endl;
    }
    
    
    return 0;
}


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

int n,m,k;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(i*j+(n-i)*(m-j)==k){
		printf("Yes\n");return 0;
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

#define ESP 1e-7

struct v3d{
	double x, y, z;

	double dot(const v3d &v) const{
		return x * v.x + y * v.y + z * v.z;
	}

	v3d sub(const v3d &v) const{
		return (v3d){x - v.x, y - v.y, z - v.z};
	}
};

typedef const v3d &cv3d;

bool intersect(cv3d s, double r, cv3d p, cv3d q){
	v3d v = q.sub(p), w = p.sub(s);
	double a = v.dot(v);
	double b = v.dot(w);
	double c = w.dot(w) - r * r;
	double D = b * b - a * c;
	if(abs(D) >= 0.0){
		D = sqrt(D);
		double t = (-b + D) / a;
		if(t >= 0.0 && t <= 1.0){ return true; }
		t = (-b - D) / a;
		if(t >= 0.0 && t <= 1.0){ return true; }
	}
	return false;
}

int main(){
	int n, m, rem;

	while(scanf("%d%d%d", &n, &m, &rem), n){
		vector<v3d> Sp(n), Tp(m);
		vector<double> Sr(n), Tb(m);
		v3d E;

		for(int i = 0; i < n; ++i){
			scanf("%lf%lf%lf%lf", &Sp[i].x, &Sp[i].y, &Sp[i].z, &Sr[i]);
		}
		for(int i = 0; i < m; ++i){
			scanf("%lf%lf%lf%lf", &Tp[i].x, &Tp[i].y, &Tp[i].z, &Tb[i]);
		}
		scanf("%lf%lf%lf", &E.x, &E.y, &E.z);

		vector<double> light(m);
		vector<bitset<2000> > intr(m);
		for(int i = 0; i < m; ++i){
			v3d dif = Tp[i].sub(E);
			light[i] = Tb[i] / dif.dot(dif);

			for(int j = 0; j < n; ++j){
				if(intersect(Sp[j], Sr[j], Tp[i], E)){
					intr[i].set(j);
				}
			}
		}

		double ans = 0.0;
		for(int i = (1 << m) - 1; i > 0; --i){
			bitset<2000> bs;
			double sum = 0.0;
			for(int j = 0; j < m; ++j){
				if(i >> j & 1){
					bs |= intr[j];
					sum += light[j];
				}
			}
			
			if(bs.count() <= rem && ans < sum){
				ans = sum;
			}
		}

		printf("%f\n", ans);

	}
}

Measured memory_bytes: 1172
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N = 5
  var a = new Array[Int](N)
  for (i <- 0 until N) {
    a(i) = sc.nextInt
  }
  val s = a.map(x => (x + 9) / 10 * 10).sum
  val loss_max = a.map(x => (s - x) % 10).max
  val result = s - loss_max
  println(result)
}

Measured memory_bytes: 27328
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  char c;
  std::cin >> c;
  std::cout << (char)(c + 1) << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

int main(){
    ll w,h,x,y;
    cin>>w>>h>>x>>y;

    cout<<fixed<<setprecision(9)<<(double)(w*h)/2<<" ";
    double cx=(double)w/2;
    double cy=(double)h/2;
    if(cx==(double)x&&cy==(double)y){
        cout<<1<<endl;
    }else{
        cout<<0<<endl;
    }
}


Measured memory_bytes: 3780
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;
typedef vector<pint> vpint;

struct Edge{int to,from,cost;};

#ifdef DEBUGLOCAL
#define debug cout
#else
stringstream __ss__;
#define debug __ss__
#endif

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) debug << *i << " "; debug << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;i--)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define repnd(i,m,n) for(int i=(n)-1;i>=(m);i--)
#define rep0(i,n) for(i=0;i<(n);++i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define SS stringstream
#define X second
#define Y first
#define PUTLINE debug<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

int solve(int n,int a){
	if(n==0)return 1;
	int res=0;
	for(int i=a;i*i<=n;++i){
		res+=solve(n-i*i,i);
	}
	return res;
}

int main() {
	int n;
	IL{
		cin>>n;
		if(n==0)break;
		cout<<solve(n,1)<<endl;
	}
	return 0;
}

Measured memory_bytes: 876
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main(void){
 
    long long N;
    cin >> N;
    
    int ans = 10;
    
    for(int i = 1; i <= sqrt(N); i++){
        if(N % i == 0){
            int A = to_string(i).size();
            int B = to_string(N/i).size();
            int keta_F = max(A, B);
            ans = min(ans, keta_F);
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::set<int> si;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
int N,T;
int A[100010];
int main(){
  cin>>N>>T;
  rep(i,N) cin>>A[i];
  int max=0,min=INF,gap=0,cnt=1;
  for(int i=N-1;i>=0;i--){
    if(max<A[i]){
      max=A[i];
      min=A[i];
    }
    if(min>A[i]){
      min=A[i];
      if(gap<max-min){
	gap=max-min;
	cnt=1;
      }
      else if(gap!=0&&gap==max-min){
	cnt++;
      }
    }
  }
  prin(cnt);
  
  return 0;
}


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

int main() {
  int n, a, b, sum = 0, aa=0,bb = 0;
  string s;
  cin >> n >> a >> b >> s;
  for (int i = 0; i < n; i++) {
    char m = s[i];
    if (m == 'a') {
      if (aa+bb+1 <= a + b) {
        cout << "Yes" << endl;
        aa++;
      } else {
        cout << "No" << endl;
      }
    }
    if (m == 'b') {
      if (aa+bb+1 <= a + b && bb+1  <= b) {
        bb++;
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }

    if (m == 'c') {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;


int main(){
	int N,M,T;
	cin>>N>>M>>T;
	int t[10001];
	fill(t,t+10001,1);
	int let;
	int ans=0;
	REP(i,0,N){
		cin>>let;
		REP(j,let-M+1,let+M+1){
			if(j>10000) break;
			t[j]=0;
		}
	}
	REP(i,1,T+1){
		ans+=t[i];
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 3132
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main()
{
  int  a, b, c, d, X, Y;
  //  double  c;
  int  A[100003]={};
  int  B[100003]={};
  int  C[100003]={};

  int  flag[103]={};

//  long long  a, b, c, d, X, Y;
//char s[101][101]={};
//  int N, M;
//  int A[1000000001]={};
//  long long  C[101]={};
  int i,j,k;
//  int flag=0;
  int tmp=0;
  int min=1000;
  int len=0;
  int cnt=0;
  int num=0;
  double ans=1000;
  int max=0;
//  char alp[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

  //  a=0;
//  scanf("%lld %lld", &a, &b);
  scanf("%d%d", &a, &b);
//  cnt = strlen(t);
  //printf("%d\n",cnt);
  if((b%a)==0)  printf("%d\n",a+b);
  else  printf("%d\n",b-a);

  
  //  //  if(flag==0)   printf("TLE\n");
//    if(max < cnt - max)  printf("Yes\n");
//    else  printf("No\n");
  
return 0;
}


Measured memory_bytes: 128
cols = input('').split()

a = int(cols[0])
b = int(cols[1])
c = int(cols[2])
x = int(cols[3])
y = int(cols[4])

total_ab = x * a + b * y

if x >= y:
    total_ac = c * y * 2 + (x - y) * a
    total_bc = c * x * 2
else:
    total_ac = c * y * 2
    total_bc = c * x * 2 + (y - x) * b

print(min(total_ab, total_ac, total_bc))

Measured memory_bytes: 3064
a, b, c, d, e, f = map(int, input().split())

water = set()
for i in range(0, f+1, 100*a):
    for j in range(0, f+1, 100*b):
        water.add(i+j)
water.remove(0)

sugar = set()
for i in range(0, f+1, c):
    for j in range(0, f+1, d):
        sugar.add(i+j)

best_w = best_s = best_dens = -1
for w in sorted(water):
    for s in sorted(sugar):
        if w + s > f:
            break
        if w * e < s * 100:
            break
        density = s / (s + w)
        if density > best_dens:
            best_w = w
            best_s = s
            best_dens = density

print(best_w + best_s, best_s)

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

ll memo[2020][2020];
int n;
vector<int> a;

ll rec(int l, int len){
  if(l>=n)l-=n;
  if(memo[l][len]>0)return memo[l][len];
  if(len <= 1)return 0;

  int L = l, R = l+len-1;
  if(R>=n)R-=n;
  if(a[L]<a[R]){
    R--; if(R<0)R+=n;
  }else{
    L++; if(L>=n)L-=n;
  }

  return memo[l][len] = max(rec(L+1,len-2)+a[L], rec(L,len-2)+a[R]);
}

int main(){
  scanf("%d",&n);
  a.resize(n);
  for(int i=0;i<n;i++)scanf("%d",&a[i]);

  ll res = 0;
  for(int i=0;i<n;i++){
    res = max( res, rec(i+1,n-1) + a[i] );
  }
  printf("%lld\n",res);
}

Measured memory_bytes: 32816
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;

#define print_container(ct,sep) cout<<*ct.begin();for(auto it=ct.begin()+1; it != ct.end(); it++) cout << sep << *it; cout << endl;
#define MOD (pow(10, 9) + 7)

#define endl '\n'
#define decimal_places(x, d) int(round(x * pow(10, d))) / double(pow(10, d))

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

    int x;
    cin >> x;

    if (x == 3 || x == 5 || x == 7)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n,m;
  cin>>n>>m;
  int a[m],b[m];
  ll c[m];
  rep(i,0,m){
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
  }
  ll d[n];
  rep(i,0,n){
    d[i]=-1e12;
  }
  d[0]=0;
  rep(j,0,n){
    rep(i,0,m){
      if(d[a[i]]!=-1e12 && d[b[i]]<d[a[i]]+c[i]){
        d[b[i]]=d[a[i]]+c[i];
      }
    }
  }
  bool p=true;
  rep(i,0,m){
    if(d[a[i]]!=-1e12 && d[b[i]]<d[a[i]]+c[i]){
      d[b[i]]=d[a[i]]+c[i];
      if(b[i]==n-1) p=false;
    }
  }
  if(p) cout<<d[n-1]<<endl;
  else cout<<"inf"<<endl;
}

Measured memory_bytes: 256
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>
#include <list>
#include <random>

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}

bool comp(const Pl &a, const Pl &b){
  return a.first < b.first;
}

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int a, b, q;
  cin >> a >> b >> q;
  vector<ll> s(a), t(b);
  rep(i, a)cin >> s[i];
  rep(i, b)cin >> t[i];
  rep(i, q){
    ll x;
    cin >> x;
    int ls = lower_bound(all(s), x) - s.begin() - 1;
    int rs = ls + 1;
    int lt = lower_bound(all(t), x) - t.begin() - 1;
    int rt = lt + 1;
    ll res = linf;
    if(ls >= 0 && lt >= 0){
      res = min(res, x - min(s[ls], t[lt]));
    }
    if(ls >= 0 && rt < b){
      res = min(res, min((ll)2 * (x - s[ls]) + t[rt] - x, (ll)2 * (t[rt] - x) + x - s[ls]));
    }
    if(rs < a && lt >= 0){
      res = min(res, min((ll)2 * (x - t[lt]) + s[rs] - x, (ll)2 * (s[rs] - x) + x - t[lt]));
    }
    if(rs < a && rt < b){
      res = min(res, max(s[rs], t[rt]) - x);
    }
    cout << res << endl;
  }
	return 0;
}


Measured memory_bytes: 2944
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
#include <cctype>
#include <fstream>   // ifstream, ofstream
#include <sstream>   // istringstream
using namespace std;
using ll = long long;
const int mod = 1000000007;
 
ll gcd(ll a, ll b){return b ? gcd(b,a%b) : a;};//最大公約数
ll lcm(ll a, ll b){return a*b/gcd(a,b);};//最小公倍数
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
typedef pair<string,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
//ll a[100000];
//ll dom[100001];
 
int main(){
  vector<char> ans;
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++){
    ans.push_back(s[i]);
  }
  int N;
  int c1=0;
  int f1=0;
  cin>>N;
  for(int i=0;i<N;i++){
    int t;
    cin>>t;
    if(t==1){
      c1++;
      f1++;
    }else if(t==2){
      int f;
      char c;
      cin>>f>>c;
      f=(f1+f)%2;
      if(f==1){
        ans.insert(ans.begin(),c);
      }else{
        ans.push_back(c);
      }
    }
  }
  if(c1%2){
    reverse(ans.begin(),ans.end());
  }
  for(int i=0;i<ans.size();i++){
    cout<<ans[i];
  }
  return 0;
}

Measured memory_bytes: 1144
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
res = 0

for i in range(2**n):
    ptn = format(i, 'b').rjust(n, '0')
    light = True
    for j in range(m):
        tmp = 0
        for k in range(1, s[j][0]+1):
            if ptn[s[j][k] - 1] == '1':
                tmp += 1
        if tmp%2 != p[j]:
            light = False
    if light:
        res += 1
print(res)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e4+5;
int a[N],b[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	ll need2=0,need1=0;
	for(int i=0;i<n;i++){
		if(a[i]>b[i]){
			need1+=a[i]-b[i];
		} 
		else if(a[i]<b[i]){
			if((b[i]-a[i])%2==0){
				need2+=(b[i]-a[i])/2;
			}
			else {
				need2+=(b[i]-a[i])/2+1;
				need1++;
			}
		}
	}
	//cout<<need1<<' '<<need2<<endl;
	if(need1<=need2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0; 
} 

Measured memory_bytes: 384
def actual(N, A):
    height_amount = 0

    for i in range(N - 1):
        left = A[i]
        right = A[i + 1]

        if left > right:
            diff = left - right
            height_amount += diff

            A[i + 1] += diff

    return height_amount
  
N = int(input())
A = list(map(int, input().split()))

print(actual(N, A))

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

#define int long long

const int N = 1e5 + 10;
int n, x, ans, ar[N];

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x;
	for (int i = 0; i < n; i++)
		cin >> ar[i];
	
	for (int i = 1; i < n; i++) {
		int tmp = max(0LL, ar[i] + ar[i - 1] - x), rem = min(tmp, ar[i]);
		ans += tmp;
		ar[i] -= rem;
		ar[i - 1] -= tmp - rem;
		assert(ar[i - 1] >= 0 && ar[i] >= 0);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#define WMAX 10000
#define HMAX 10000

//コメントアウトするとdebug()を実行しない
#define DEBUG

using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

struct edge{
  int to,cost;
};

long long A,B,C,D,N,W,H,ans,L[79] = {};
string S;
static const int dx[8] = {0,1,1,1,0,-1,-1,-1},
					dy[8] = {1,1,0,-1,-1,-1,0,1};

void solve(){
	L[0] = 2;
	L[1] = 1;
	for (int i = 2; i <= N; ++i)
	{
		L[i] = L[i-1] + L[i-2];
	}
	ans = L[N];
}

void debug(){

}

void answer(){
	cout << ans << "\n";
}

int main(){
	cin >> N;
	solve();
	#ifdef DEBUG
	debug();
	#endif
	answer();

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double nonTax = N / 1.08;
        double reCalc = 0;
        while(reCalc < N){
            nonTax -= nonTax % 1;
            reCalc = nonTax * 1.08;
            reCalc -= reCalc % 1;
            nonTax += 1;
            if(reCalc == N) {
                nonTax -= 1;
                System.out.println((int)nonTax);
            }
        }
        if(reCalc >= N+1){
            System.out.println(":(");
        }
    }
}


Measured memory_bytes: 23892
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

	

	int m[50] = { 0 };
	int f[50] = { 0 };
	int r[50] = { 0 };

	int temp_m, temp_f, temp_r;

	int i = 0;
	for (; i < 50; i++) {
		scanf("%d %d %d", &temp_m, &temp_f, &temp_r);
		if (temp_m == -1 && temp_f == -1 && temp_r == -1) {
			break;
		}
		m[i] = temp_m;
		f[i] = temp_f;
		r[i] = temp_r;
	}
	

	int j = 0;
	for (j = 0; j < i; j++) {
		if (m[j] == -1 || f[j] == -1) {
			printf("F\n");
		}else if(m[j] + f[j] >=80){
			printf("A\n");
		}
		else if (m[j] + f[j] >= 65) {
			printf("B\n");
		}
		else if (m[j] + f[j] >= 50) {
			printf("C\n");
		}
		else if (m[j] + f[j] >= 30) {
			if (r[j] >= 50) {
				printf("C\n");
			}
			else {
				printf("D\n");
			}
		}
		else {
			printf("F\n");
		}
	}
	

	return 0;
}


Measured memory_bytes: 2056
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base :: sync_with_stdio(0),cin.tie(0)
#define file() freopen("in.txt","r",stdin)



int main()
{
 // IO;
 // file();
  int i,j,k,n,t;
  cin>>t;
  if(t==0) cout<<1<<endl;
  else if(t==1) cout<<0<<endl;

 
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
using ll = long long;

int main(){
  string s;
  cin>>s;
  int n=s.size();
  rep(i,n/2){
    if(s[i]!=s[n-i-1]){
      cout<<"No"<<endl;
      return(0);
    }
  }
  int m=n/2;
  rep(i,m/2){
    if(s[i]!=s[m-i-1]){
      cout<<"No"<<endl;
      return(0);
    }
  }
  int k=(n+2-1)/2;
  rep(i,m/2){
    if(s[k+i]!=s[k+m-i-1]){
      cout<<"No"<<endl;
      return(0);
    }
  }
  cout<<"Yes"<<endl;
  return(0);
}


Measured memory_bytes: 256
n=int(input())
alist=list(map(int,input().split()))

alist.sort()
gomi=0
for i in range(1,n):
    if alist[i]==alist[i-1]:
        gomi+=1
if gomi%2==0:
    ans=n-gomi
else:ans=n-gomi-1
print(ans)


Measured memory_bytes: 14396
n = int(input())
a = [int(x) for x in input().split(' ')]

a.sort()
a_max = a[-1] + 1   # aの最大値
lst = [0] * a_max   # a_max個のリストを生成

for x in a:
    lst[x] += 1                         # リストの該当の数字に1追加 
    if lst[x] == 1:                     # まだ他の数値の倍数でなければ、リストへ2倍、3倍…の数字を1追加していく
        for i in range(x*2, a_max, x):
            lst[i] += 1

output = 0
for x in a:
    if lst[x] == 1:
        output += 1
print(output)

Measured memory_bytes: 32184
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 200005
using namespace std;

int n,m,q,sx,sy;
char s[M], t[M];

char inv(char x) {
    if (x=='U') return 'D';
    if (x=='D') return 'U';
    if (x=='L') return 'R';
    if (x=='R') return 'L';
    return 0;
}
bool check(char mx,char my) {
    int x = sx;
    int y = sy;
    REP(i,1,q) {
        if (s[i]==mx) {
            x += mx=='U' ? -1 : 1;
        }
        if (s[i]==my) {
            y += my=='L' ? -1 : 1;
        }
        if (x<=0 || x>n || y<=0 || y>m) return true;

        if (t[i]==inv(mx)) {
            x += inv(mx)=='U' ? -1 : 1;
            if (x<=0 || x>n) x -= inv(mx)=='U' ? -1 : 1;
        }
        if (t[i]==inv(my)) {
            y += inv(my)=='L' ? -1 : 1;
            if (y<=0 || y>m) y -= inv(my)=='L' ? -1 : 1;
        }
        //printf("%d %d\n",x,y);
        //if (x<=0 || x>n || y<=0 || y>m) return true;
        
    }

    return false;
}

int main()
{
    while (~scanf("%d %d %d",&n,&m,&q)) {
        scanf("%d %d",&sx,&sy);
        scanf("%s", s+1);
        scanf("%s", t+1);

        if (check('U', 'L') || check('U', 'R') || check('D', 'L') || check('D', 'R')) {

            puts("NO");
        } else {
            puts("YES");
        }
    }
    
    return 0;
}






Measured memory_bytes: 640
MOD = 1000000007

X,Y = map(int,input().split())
x,y = (2*X-Y)//3,(2*Y-X)//3#行動１、行動２を起こす回数
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or x < 0 or y < 0 or(x==0 and y==0):
    print(0)
    exit()
ans =1
for i in range(x+y,0,-1):
    ans = ((ans%MOD)*i)%MOD
for i in range(x,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD
for i in range(y,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD

print(ans)


Measured memory_bytes: 42268
use std::io;

fn read_line()-> String {
    let mut s = String::new();
    let _ = io::stdin().read_line(&mut s).unwrap();
    s
}

fn main() {
    let x = read_line().trim().parse::<i32>().unwrap();
    if x >= 1200 {
        println!("ARC");
    }else{
        println!("ABC");
    }
}

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

using namespace std;

using ll = long long int;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define scanInt(x) int x; scanf("%d", &(x)); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &(x)); getchar();
#define scanVecInt(A, N) vector<int> A(N); REP(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); REP(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanLLInt(N);
    scanLLInt(C);
    vector<pair<ll, ll>> forward; forward.reserve(N);
    vector<pair<ll, ll>> back; back.reserve(N);
    REP(i, N){
        scanLLInt(xi);
        scanLLInt(vi);
        // forward.emplace(xi, vi);
        // back.emplace(xi, vi);
        forward.emplace_back(xi, vi);
    }
    for (int i = N - 1; 0 <= i; --i){
        back.emplace_back(forward[i].first, forward[i].second);
    }
    // for (auto& l : forward) cout << l.first << " " << l.second << endl;
    // for (auto& l : back) cout << l.first << " " << l.second << endl;
    vector<ll> fscore(N);
    vector<ll> bscore(N);
    vector<ll> fd(N);
    vector<ll> bd(N);
    {
        ll temp = 0;
        ll x = 0;
        ll temp2 = 0;
        REP(i, N){
            auto& e = forward[i];
            temp += e.second - abs(e.first - x);
            fscore[i] = temp;
            temp2 = max(temp2, temp - e.first);
            fd[i] = temp2;
            x = e.first;
        }
    }
    {
        ll temp = 0;
        ll x = C;
        ll temp2 = 0;
        REP(i, N){
            auto& e = back[i];
            temp += e.second - abs(e.first - x);
            bscore[i] = temp;
            temp2 = max(temp2, temp - (C - e.first));
            bd[i] = temp2;
            x = e.first;
        }
    }
    ll result = 0;
    REP(i, N){
        // cout << fscore[i] << " " << fd[i] << " " << bscore[i] << " " << bd[i] << " " << fscore[i] + ((0 <= N - i - 2) ? bd[N - i - 2] : 0) << " " << bscore[i] + ((0 <= N - i - 2) ? fd[N - i - 2] : 0) << endl;
        result = max(result, fscore[i]);
        result = max(result, bscore[i]);
        result = max(result, fscore[i] + ((0 <= N - i - 2) ? bd[N - i - 2] : 0));
        result = max(result, bscore[i] + ((0 <= N - i - 2) ? fd[N - i - 2] : 0));
    }
    cout << result << endl;
}


Measured memory_bytes: 6528
// first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
const ll mod = 1e9 + 7 ;
void add_self(ll& a , ll b){a =  (a + b)%mod;}
// #define a(x)  get<0>(x) 
// #define b(x)  get<1>(x)
//#define (x)  get<2>(x)
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n , w ;cin>>n>>w ; 
ll arr[n] ,brr[n];
for(ll i = 0 ; i<n ; i++)cin>>arr[i]>>brr[i] ; 

vector<vector<ll>> dp(n , vector<ll>(w+1));

for(ll i = arr[0] ; i<=w ; i++)dp[0][i] = brr[0] ; 

for(ll i = 1 ; i<n ; i++){
	for(ll j = 0 ; j<arr[i] ; j ++)dp[i][j] = dp[i-1][j];
	for(ll j = arr[i] ; j <= w ; j++){
		// if(j-arr[i]>=0)
		dp[i][j] =  max(max(dp[i][j],max(dp[i][j-1],dp[i-1][j])) , brr[i] + dp[i-1][j-arr[i]]);
	}
}
// for(auto i:dp){
// 	for(auto j:i)cout<<j<<" ";
// 		cout<<endl;
// }

cout<<dp[n-1][w];




	
}

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

#define int long long
#define MOD 1000000007


#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define all(i) (i).begin(),(i).end()å
#define rall(i) (i).begin(),(i).end(),greater<int>()
using namespace std;

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T> void print(T x) { std::cout << x << '\n'; }
 
//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

 
signed main(){
 
    int a[5];

    rep(i,5){
        cin >>a[i];
    }
    int sum=0;

    vector<int> amari;

    rep(i,5){
        string temp = to_string(a[i]);
        int c = temp[temp.size()-1]-'0';
        if(c!=0){        
            amari.pb(10-c);
        }
        temp.clear();
    }

    if(amari.size()>1){
        sort(amari.begin(),amari.end());
    }

    rep(i,5){
        sum = sum + a[i];
    }

    if(amari.size()>1){
        for(int i=0;i<amari.size()-1;i++){
            sum = sum + amari[i];
        }
    }

    cout <<sum<<endl;

    return 0;
 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    int n;
    cin >> n;
    vector<int> p(n+10);
    for(int i = 1; i <= n; i++) cin >> p[i];
    int cnt = 0;
    if(p[1] == 1){
        swap(p[1],p[2]);
        cnt++;
    }
    for(int i = 1; i < n; i++){
        if(p[i] == i){
            swap(p[i],p[i+1]);
            cnt++;
        }
    }
    if(p[n] == n) cnt++;
    cout << cnt << endl;
    return 0;
}


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

int main()
{
	vector<int> mt;
	for (int i = 0; i < 10; i++) {
		int tmp;
		cin >> tmp;
		mt.push_back(tmp);
	}
	sort(mt.begin(), mt.end());
	for (int i = mt.size()-1, j = 0; j < 3; i--, j++) {
		cout << mt[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
int GCD(int x, int y) {
    return x ? GCD(y % x, x) : y;
}
int main(){
int n;cin>>n;
vector<int> k(n);
for(int i=0;i<n;i++) cin>>k.at(i);
int s=k[0];
for(int i=0;i<n;i++) s=GCD(s,k.at(i));
cout<<s<<endl;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    int ans = 0;
    vector<int> dist(n, 0);
    rep(i, n - 1) {
        int s;
        cin >> s;
        dist[i + 1] = dist[i] + s;
    }
    int before = 0;
    while (m--) {
        int a;
        cin >> a;
        ans += dist[max(before, a + before)] - dist[min(before, a + before)];
        before += a;
        ans %= (int)1e5;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int i,j,count=0;
    int x=s.size();
    for(i=0,j=x-1;i<=j;i++,j--){
        if(s[i]!=s[j])
        count++;
    }
    cout<<count<<endl;
}


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
const int MX = 100005;
const int MOD = 1e9+7;
int n;
ll d, a, b, x, y, c, ac[MX], ans;
ll exgcd(ll a, ll b, ll &x, ll &y){
	if(b){
		exgcd(b, a%b, y, x);
		y = (y - a/b*x%MOD + MOD) % MOD;
	}else{
		x = 1; y = 0;
	}
	return x;
}
int main(){
	scanf("%d", &n);
	rep(i,n) ac[i+1] = (ac[i] + exgcd(i+1,MOD,x,y)) % MOD;
	rep(i,n){
		scanf("%lld", &c);
		ans = (ans + (ac[i+1] + ac[n-i] - 1) * c) % MOD;
	}
	rep(i,n) ans = ans * (i+1) % MOD;
	printf("%lld\n", ans);
}

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

using ll = long long;

const int N = 100005;

int n, d[N], c[N], p[N], q, t;
vector<int> e[N], r, s;

void f(int x, int y){
    int u = int(e[x].size()) - d[x];
    if(d[x] == 1){
        if(!q){
            p[1] = q++;
            for(int i = t + 2; i <= t + u; i++) p[i] = q++;
            p[2] = q++;
            t += (u + 1); 
        }
        else{
            for(int i = t + 1; i < t + u; i++) p[i] = q++;
            p[t] = q++;
            p[n] = q++;
        }
    }
    else{
        for(int i = t + 1; i <= t + u; i++) p[i] = q++;
        p[t] = q++;
        t += (u + 1);
    }
    for(int i : e[x]) if(i != y && d[i]) f(i, x);
}

int main(){
    scanf("%d", &n);
    if(n == 1){ puts("1"); return 0; }
    for(int i = 0, x, y; i < n - 1; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    
    for(int i = 1; i <= n; i++) c[i] = (e[i].size() > 1);
    for(int i = 1; i <= n; i++) for(int j : e[i]) if(c[i] && c[j]) d[i]++;
    if(count(d + 1, d + n + 1, 1) > 2){ puts("-1"); return 0; }
    
    if(count(d + 1, d + n + 1, 1) == 0){
        printf("1 ");
        for(int i = 3; i <= n - 1; i++) printf("%d ", i);
        printf("2 %d", n);
        return 0;
    }

    q = 0; t = 1;
    for(int i = 1; i <= n; i++) if(d[i] == 1){ f(i, 0); break; }
    r.resize(n);
    for(int i = 1; i <= n; i++) r[p[i]] = i;
    
    q = 0; t = 1;
    for(int i = n; i >= 1; i--) if(d[i] == 1){ f(i, 0); break; }
    s.resize(n);
    for(int i = 1; i <= n; i++) s[p[i]] = i;
    
    r = min(r, s);
    for(int i : r) printf("%d ", i);
    puts("");
}


Measured memory_bytes: 12928
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int mod = MOD9;
const int max_n = 300005;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(max_n);
int main(){
    ll n,a,b,k;cin >> n >> a >> b >>k;
    mint ans=0;
    rep(i,n+1){
        if((k-a*i)%b!=0||(k-a*i)<0)continue;
        ll x=i,y=(k-a*i)/b;
        mint res=comb(n,x);
        res*=comb(n,y);
        ans+=res;
    }
    cout << ans <<endl;
}

Measured memory_bytes: 4992