akhauriyash/Code-Regression huggingface dataset:
s = list(input())
acgt = ['A', 'C', 'G','T']
lst = []
for c in s:
    if c in acgt:
        lst.append(c)
    else:
        lst.append(" ")
ans = "".join(lst).split()
ln = list(map(len, ans))
if len(ln) > 0:
    print(max(ln))
else:
    print(0)

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

#define ll long long
#define ar array

string n;
int k, m;

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

    cin >> n >> k;
    int m = n.size(), ans = 0;
    for (int i = 0; i < m; ++i)
    {
        for (int d1 = 1; d1 <= 9; ++d1)
        {
            if (i == 0 && d1 > n[0] - '0')
                continue;
            bool less1 = i || d1 < n[0] - '0';
            if (k == 1)
            {
                ++ans;
            }
            else
            {
                for (int j = i + 1; j < m; ++j)
                {
                    for (int d2 = 1; d2 <= 9; ++d2)
                    {
                        if (!less1 && d2 > n[j] - '0')
                            continue;
                        bool less2 = less1 || d2 < n[j] - '0';
                        if (k == 2)
                        {
                            ++ans;
                        }
                        else
                        {
                            for (int k = j + 1; k < m; ++k)
                            {
                                for (int d3 = 1; d3 <= 9; ++d3)
                                {
                                    if (!less2 && d3 > n[k] - '0')
                                        continue;
                                    ++ans;
                                }
                                if (n[k] > '0')
                                    less2 = 1;
                            }
                        }
                    }
                    if (n[j] > '0')
                        less1 = 1;
                }
            }
        }
    }
    cout << ans;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] a = new int[n];
		double sum = 0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			sum += a[i];
		}
		double average = sum / n;
		double min = 101;
		int minIdx = -1;
		for (int i = 0; i < n; i++) {
			if (min > Math.abs(average - a[i])) {
				min = Math.abs(average - a[i]);
				minIdx = i;
			}
		}
		System.out.println(minIdx);
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
struct edge{int from, to; ll cost;};
const ll INF = 1e17;

bool bellman_ford(int n, int s, vector<edge>& es, vector<ll>& d){
  rep(i,n) d[i] = INF;
  d[s] = 0;
  bool negative_loop = false;
  rep(i,n) {
    bool update = false;
    for(auto e : es) {
      if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
        if(i == n-1) negative_loop = true;
        d[e.to] = d[e.from] + e.cost;
        update = true;
      }
    }
    if(!update) break;
  }
  return negative_loop;
}

int main(){
  int v, e, r;
  cin >> v >> e >> r;
  vector<edge> es;
  rep(i,e) {
    int s, t; ll dist;
    cin >> s >> t >> dist;
    es.push_back(edge{s,t,dist});
  }
  vector<ll> d(v);
  bool f = bellman_ford(v,r,es,d);
  if(f) cout << "NEGATIVE CYCLE" << endl;
  else rep(i,v) cout << (d[i] == INF ? "INF" : to_string(d[i])) << endl;
  return 0;
}


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

int main() {
    int n, k;
    while(cin >> n >> k, n) {
        vector<int> a(k);
        vector<int> s(n + 2, 1);
        s[0] = s.back() = 0;
        int w = 0;
        for(int i = 0; i < k; ++i) {
            cin >> a[i];
            if(a[i] == 0) {
                w = 1;
            } else {
                s[a[i]] -= 1;
            }
        }
        for(int i = 0; i < n + 1; ++i) {
            s[i + 1] += s[i];
        }

        int ans = 0;
        for(int i = 0; i < n; ++i) {
            auto check = [&] (int x) {
                return s[x] - s[i] <= w;
            };
            int lb = i, ub = n + 1;
            while(ub - lb > 1) {
                const int mid = (ub + lb) >> 1;
                (check(mid) ? lb : ub) = mid;
            }
            ans = max(ans, ub - i - 1);
        }
        cout << ans << endl;
    }
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

int main() {
	int n, m,ma=-200;
	cin >> n;
	map<string, int> card;
	rep(i, n) {
		string s;
		cin >> s;
		if (card.find(s) == card.end()) {
			card[s] = 1;
		}
		else {
			card[s]++;
		}
	}
	cin >> m;
	rep(i, m) {
		string s;
		cin >> s;
		if (card.find(s) != card.end()) {
			card[s]--;
		}
	}
	for (auto c : card) {
		ma = max(c.second, ma);
	}
	cout << (ma < 0 ? 0 : ma) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  int main(){
      int H,W;
      char ch;
      int a[200][200],sumH[200],sumW;
      scanf("%d%d",&H,&W);
      for(int i=0;i<H;i++)
        for(int j=0;j<W;j++){
            scanf("%c",&ch);
            while((ch!='.')&&(ch!='#'))scanf("%c",&ch);
            if(ch=='.')a[i][j]=0;
            else a[i][j]=1;            
        }
      for(int i=0;i<H;i++){
          sumH[i]=0;
          for(int j=0;j<W;j++)sumH[i]+=a[i][j];
      }
      for(int j=0;j<W;j++){
          sumW=0;
          for(int i=0;i<H;i++)sumW+=a[i][j];
          if(sumW==0){
              for(int i=0;i<H;i++)a[i][j]=-1;
          }
      }
      for(int i=0;i<H;i++){
          if(sumH[i]>0){
              for(int j=0;j<W;j++){
                  if(a[i][j]==0)printf(".");
                  else if(a[i][j]==1)printf("#");
              }
              printf("\n");
          }
      }
      
      return 0;
  }

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <assert.h>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
using namespace std;

// #define __DEBUG__

#ifdef __DEBUG__
bool debug_disabled = false;
#else
bool debug_disabled = true;
#endif

#define dbg if (debug_disabled) {} else cerr

const int MOD = 1000000007;

long long nums[200010];
long long suff_sums[200010];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> nums[i];
    for (int i = n - 2; i >= 0; --i) suff_sums[i] = (nums[i + 1] + suff_sums[i + 1]) % MOD;
    long long res = 0;
    for (int i = 0; i < n; ++i) {
        long long tres = (nums[i] * suff_sums[i]) % MOD;
        res = (res + tres) % MOD;
    }
    cout << res << endl;
}

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout.precision(12);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}


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

#define ll long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define sizeOf(A) (sizeof(A))/(sizeof(A[0]))
#define odd(x) ((x) % (2))
#define fastio ios_base::sync_with_stdio(false), cin.tie(0);
const ll MOD = 1e9 + 7;

int main() {
    fastio;

    string s;
    cin >> s;
    if (s[0] == '9' || s[1] == '9') {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < s.size(); i++)s[i] == '+' ? ans++ : ans--;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using std::cout;
using std::vector;
using std::endl;
using std::cin;
using std::string;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
constexpr int MOD = 1000000007;
constexpr ll INF = 50000000000000000;
typedef std::pair<int,int> P;
constexpr ll SIZE= 100010;

    ll N,A,B,C,D;
    ll ans=0,sum=0,wa=0;
    ll gcd(ll a,ll b){
        if(b==0)return a;
        return gcd(b,a%b);
    }
int main() {
    std::ios_base::sync_with_stdio(false);
    cin>>N;
    REP(i,N){
       cin>>A>>B>>C>>D;
       if(A<B||D<B){cout<<"No"<<endl;continue;}
       cout<<(B-gcd(B,D)+A%gcd(B,D)<=C?"Yes":"No")<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
n=int(input())
l=list(list(input().split() for i in range(n)))
ans=0
for j in range(n):
   if l[j-1][1]=='JPY':
       ans+=float(l[j-1][0])
   else:
       ans+=float(l[j-1][0])*380000
print(ans)   
   


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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

using Int = long long;

int N, M;
vector<Int> x, y, z;
Int dp[1003][1003];
bool used[1003][1003];
Int dfs(int i, int rest, int S) {
    if (i == N) {
        if (rest == 0) return 0;
        return -1e18;
    }
    if (used[i][rest]) return dp[i][rest];
    Int ret;

    ret = dfs(i + 1, rest, S);
    if (rest) {
        Int xs = 0, ys = 0, zs = 0;
        if (S >> 0 & 1) {
            xs += x[i];
        } else {
            xs -= x[i];
        }
        if (S >> 1 & 1) {
            ys += y[i];
        } else {
            ys -= y[i];
        }
        if (S >> 2 & 1) {
            zs += z[i];
        } else {
            zs -= z[i];
        }
        Int sum = xs + ys + zs;
        ret = max(ret, dfs(i + 1, rest - 1, S) + sum);
    }
    used[i][rest] = true;
    return dp[i][rest] = ret;
}

int main() {
    cin >> N >> M;
    x.resize(N);
    y.resize(N);
    z.resize(N);
    rep(i, N) cin >> x[i] >> y[i] >> z[i];

    Int ans = 0;
    rep(S, 1 << 3) {
        rep(i, 1003) rep(j, 1003) {
            dp[i][j] = -1;
            used[i][j] = false;
        }
        // Int t = dfs(0, M, S);
        // cout << S << ", " << t << endl;
        ans = max(ans, dfs(0, M, S));
    }
    cout << ans << endl;

    return 0;
}


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

int main(void){
    int n;
    vector<int> ps;
    cin >> n;
    int input;
    for(int i = 0; i < n; i++){
        cin >> input;
        ps.push_back(input);
    }

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

    int mid = n / 2;
    if(ps[mid - 1] == ps[mid]) cout << 0 << endl;
    else cout << ps[mid] - ps[mid - 1] << endl;
  
  	return 0;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int n;
string s[2];

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
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 {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=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 {
        mint res(*this);
        return res/=a;
    }
};

int main() {
    cin>>n>>s[0]>>s[1];

    int pre=-1;
    int x=0;
    ll ans=1;
    while(x<n){
        if(s[0][x]==s[1][x]){
            if(pre<0) ans=3;
            else if(pre==0) ans*=2;
            else ans*=1;
            ans%=MOD;
            x++;
            pre=0;
        }
        else{
            if(pre<0) ans=6;
            else if(pre==0) ans*=2;
            else ans*=3;
            ans%=MOD;
            x+=2;
            pre=1;
        }
    }
    cout<<ans<<endl;
}

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

#define FAST {ios::sync(false);}
#define pb push_back
#define fi first
#define se second
#define pii pair<long long int,long long int>
#define ll long long int
#define f(i,a,b) for(int i=a;i<b;i++)

int main(){

    // FAST
    ll n,w;
    cin>>n>>w;

    vector<pii> arr(n+1);
    for(ll i =1; i<=n; i++){
        ll wt,val;
        cin>>wt>>val;
        arr[i] = {wt, val};
    }
    sort(arr.begin(),arr.end());

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

    for(ll i=1;i<=n;i++){
        auto elem = arr[i];
        for(ll j=1;j<=w;j++){
            if(elem.fi > j){
                knap[i][j] = knap[i-1][j];
                continue;
            }
            ll temp =  max(knap[i-1][j],elem.se+knap[i-1][j-elem.fi]);
            knap[i][j] = max(knap[i][j],temp);
        }
    }

    // f(i,0,n+1){
    //     f(j,0,w+1){
    //         cout<<knap[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    cout<<knap[n][w]<<"\n";
    return 0;
}

Measured memory_bytes: 83004
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 100011

int n, i, x, mini, maxi;
int cnt[maxN], l, r;

void No() {
    cout << "No";
    exit(0);
}

void Yes() {
    cout << "Yes";
    exit(0);
}

int main()
{
    //freopen("test.in","r",stdin);

    scanf("%d", &n);
    mini = n + 13;
    maxi = -1;

    for (i = 1; i <= n; i++) {
        scanf("%d", &x);
        mini = min(mini, x);
        maxi = max(maxi, x);
        cnt[x]++;
    }

    if (maxi - mini > 1)
        No();

    if (maxi == mini) {
        if (maxi == n - 1)
            Yes(); //! all are 1

        l = 1; r = n / 2;
        if (l <= maxi && maxi <= r)
            Yes();
        else
            No();
    } else {
        int gr_small = cnt[mini];
        l = gr_small + 1;
        r = gr_small + (cnt[maxi] / 2);

        if (l <= maxi && maxi <= r)
            Yes();
        else
            No();
    }



    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
int main(void){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	if(x-r>=0 && x+r<=W && y-r>=0 && y+r<=H){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
import math
while True:
 n = int(input())
 if n==0:
  break
 S = list(map(int, input().split() ))
 m = sum(S)/n
 S2 = S
 for si in range(n):
  S2[si] = (S[si]-m)**2
 SS = sum(S2)/n
 sd = math.sqrt(SS)
 print(sd)
 


Measured memory_bytes: 5696
#include <bits/stdc++.h>
#define rep0(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<string,int, int> TU;

int main()
{
    int a,b,c,d,e,k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e-a<=k){
        cout << "Yay!";
    }    else{
        cout << ":(";
    }
}
	


Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main(){
	int a, b, c;
	cin >> a >> b >>c;
	
	if ( a >= b ) cout << "No"  << endl;
	else if ( a >= c ) cout << "No"  << endl;
	else if ( b >= c ) cout << "No"  << endl;
	else cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 3072
#include<stdio.h>
int main(){
	int a,b,c,d,e,k;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&k);
	if(e-a<=k&&e-b<=k&&e-c<=k&&e-d<=k&&d-c<=k&&d-b<=k&&d-a<=k&&c-b<=k&&c-a<=k&&b-a<=k){
		printf("\nYay!");
		}else{
		printf("\n:(");
	}
	return 0;
}

Measured memory_bytes: 128
#include <queue>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M; string S;
	cin >> N >> M >> S;
	vector<vector<int> > G(N);
	vector<int> rc(N), bc(N);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
		if (S[b] == 'A') ++rc[a];
		else ++bc[a];
		if (S[a] == 'A') ++rc[b];
		else ++bc[b];
	}
	int cnt = 0;
	queue<int> que;
	for (int i = 0; i < N; ++i) {
		if (rc[i] == 0 || bc[i] == 0) {
			que.push(i);
		}
	}
	while (!que.empty()) {
		int u = que.front(); que.pop();
		++cnt;
		for (int i : G[u]) {
			if (rc[i] >= 1 && bc[i] >= 1) {
				if (S[u] == 'A') --rc[i];
				else --bc[i];
				if (rc[i] == 0 || bc[i] == 0) {
					que.push(i);
				}
			}
		}
	}
	cout << (cnt != N ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 12240
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)

using namespace std;

int N, K, A[100005];

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

    cin >> N >> K;
    REP(i, N) cin >> A[i];

    int ans = 1 + (N - K) / (K - 1);
    if ((N - K) % (K - 1) != 0) ans++;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n];
    int b=0;
    for(int k=0;k<n;k++){
        cin>>a[k];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(a[i]==a[i+1]){
            cout<<"NO";
            b=1;
            break;
        }
    }
    if(b==0){
        cout<<"YES";
    }
}


Measured memory_bytes: 1024
while True:
    string = input()
    numbers = list(map(int, string.split(' ')))
    if numbers[0] == 0 and numbers[1] == 0:
        break
    for i in range(numbers[0]):
        for j in range(numbers[1]):
            if (i + j) % 2 == 0:
                print('#', sep='', end='')
            else:
                print('.', sep='', end='')
        print()
    print()


Measured memory_bytes: 7000
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n, k, ai;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> ai;
    
    cout << ceil((n - 1) / (k - 1)) + ((n - 1) % (k - 1) ? 1 : 0) << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    d, t, s = list(map(int,input().split()))
    if d/s <= t:
        print('Yes')
    else:print('No')
    return 0

if __name__ == "__main__":
    main()

Measured memory_bytes: 27168
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    char a,b;
    while(scanf("%c %c",&a,&b)!=EOF)
    {
        getchar();
        if(a=='H')
        {
            printf("%c",b);
        }
        else
        {
            if(b=='H')
                printf("D");
            else
                printf("H");
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 256
// luogu-judger-enable-o2
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
char s[100007];
int get[128];
int main()
{
    get['b'] = 0 , get['p'] = 1 , get['d'] = 2 , get['q'] = 3;
    scanf("%s",s+1); // 从 s[1] 开始的
    for(int l = strlen(s+1), i = 1; i <= (l>>1) + 1; ++i)
    {
        if(get[s[i]]^((get[s[l-i+1]]+2)%4)) return printf("No\n"),0;
    } // 这个 +2 %4 刚好让 b 转到 d 上， d 转到 b 上， p 转到 q 上， q 转到 p 上 
    return printf("Yes\n"),0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();

    string s;
    cin >> s;
    vector<string> f = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    cout << 7 - (find(all(f), s)-f.begin()) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>
#include <math.h>
#include <numeric>
#include <sstream>
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    if (n == 7 || n == 5 || n == 3) {
        cout << "YES" << std::endl;
    } else {
        cout << "NO" << std::endl;
    }
    return 0;
}

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;

  if((abs(b-a)<=d&&abs(c-b)<=d)||abs(c-a)<=d){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

}



Measured memory_bytes: 256
n=int(input())
if n==0:
    print(0)
    exit()
s=list(str(bin(n)))[2:][::-1]
t=[0]*(len(s)+2)
for i in range(len(s)):
    if s[i]=="1":
        if n>=0:
            if i%2==0:
                t[i]+=1
            else:
                t[i]+=1
                t[i+1]+=1
        else:
            if i%2==0:
                t[i]+=1
                t[i+1]+=1
            else:
                t[i]+=1
    else:
        pass
for i in range(len(t)):
    if t[i]==2:
        if i%2==1:
            t[i]=0
            if t[i+1]>0:
                t[i+1]-=1
            else:
                t[i+1]+=1
                t[i+2]+=1
        else:
            t[i]=0
            t[i+1]+=1
            t[i+2]+=1
t=t[::-1]
i=0
while t[i]==0:
    i+=1
print("".join(map(str,t[i:])))
    

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first 
#define ss second  
typedef pair<ll,ll> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
} 
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=(a*res)%10;
        }
        a=(a*a)%10;
        b/=2;
    }
    return (res%10);
} 
void solve(){
    char c;
    cin>>c;
    if(c<='Z') cout<<"A";
    else cout<<"a";
}
int main() {
	// your code goes here
	//isprime();
	//prime(); 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//int t;
	//cin>>t;
	//while(t--) 
	    solve();
	return 0; 
	
}


Measured memory_bytes: 3568
#include <cstdio>
#include <numeric>
 
int const N = 1000001;
 
int spf[N], u[N], s[17], d, i, j, k;
char const* r = "pairwise";
 
int main() {
    while (++i < N)spf[i] = i;
    for (i = 2; i * i < N; i++)
        for (j = i * i; j < N; j += i)
            if (spf[j] == j) spf[j] = i;
    for (scanf("%*d"); ~scanf("%d", &j); k = 0) {
        d = std::gcd(d, j);
        for (; j > 1; j /= i) {
            s[k++] = i = spf[j];
            if (u[i]) r = "setwise";
        }
        while(k--) u[s[k]] = 1;
    }
    printf("%s coprime\n", d > 1 ? "not" : r);
    return 0;
}


Measured memory_bytes: 9548
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    int n,k;
    cin>>n>>k;
    ll ans=0;
    for(int i=1;i<=k;++i){
        int t=k/i;
        vector<ll> num(t+1,0);
        for(int j=t;j>=1;--j){
            num[j]=(num[j]+modpow(t/j,n))%mod;
            for(ll r=1;r*r<=j;++r){
                if(j%r==0&&j!=r){
                    num[r]=(num[r]-num[j]+mod)%mod;
                    if(r*r!=j&&r!=1){
                        num[j/r]=(num[j/r]-num[j]+mod)%mod;
                    }
                }
            }
        }
        ans=(ans+num[1]*i)%mod;
    }
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
}


Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define ALL(v) (v).begin(), (v).end()
#define PUTS(x) cout << (x) << endl;
#define PB push_back
#define MP make_pair
vector<Int> IntsIn(int n) {
    auto v = vector<Int>(0);
    for (int i = 0; i < n; i++) {
        Int a;
        cin >> a;
        v.push_back(a);
    }
    return v;
}


int main() {
    std::cout << std::fixed << std::setprecision(30);
    long double x;
    cin >> x;
    PUTS((x / 3) * (x / 3) * (x / 3));
}


Measured memory_bytes: 256
package main

import "fmt"


func main() {
	var (
		a, b, c, x, count int
	)
	fmt.Scan(&a, &b, &c, &x)
	for i := 0; i < a+1; i++ {
		for j := 0; j < b+1; j++ {
			for k := 0; k < c+1; k++ {
				if i*500+j*100+k*50 == x {
					count++
				}
			}
		}
	}
	fmt.Println(count)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll q, h, s, d, n;

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> q >> h >> s >> d >> n;
    h = min(h, q * 2);
    s = min(s, h * 2);
    d = min(d, s * 2);
    cout << (n / 2) * d + (n % 2) * s << endl;

    return 0;
}


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


int main(){
  vector<int> a(4), b(4);

  while(cin >> a[0]){
    cin >> a[1] >> a[2] >> a[3];
    cin >> b[0] >> b[1] >> b[2] >> b[3];

    int hit = 0, blow = 0;

    for(int i=0; i<4; i++){
      for(int j=0; j<4; j++){
        if(a[i] == b[j]){
          if(i == j){
            hit++;
          } else {
            blow++;
          }
        }
      }
    }
    cout << hit << " " << blow << endl;
  }
}
  
  


Measured memory_bytes: 3020
#include <iostream>

using namespace std;

int main()
{
    int t; cin >> t;
    int ac = 0, wa =0, tle =0, re= 0;

    while(t--)
    {
        string s;
        cin >> s;
        if(s == "AC")
        {
            ac++;
        }
        else if(s == "WA")
        {
            wa++;
        }
        else if(s == "TLE")
        {
            tle++;
        }
        else if(s == "RE")
        {
            re++;
        }
    }
    cout << "AC x" << " " << ac << endl;
    cout << "WA x" << " " << wa << endl;
    cout << "TLE x" << " " << tle << endl;
    cout << "RE x" << " " << re << endl;
    return 0;
}


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

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        long h = in.nextLong();

        long ans = 0;
        long count = 1;
        while (h >= 1) {
            ans += count;
            count *= 2;
            h /= 2;
        }
        out.println(ans);
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        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;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 22484
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
dist = [[None]*W for _ in range(H)]

stack = deque([])
for h in range(H):
    for w in range(W):
        if maze[h][w]=="#":
            stack.append((h,w))
            dist[h][w] = 0

ans = 0
while stack:
    ch,cw = stack.popleft()
    ans = max(ans, dist[ch][cw])
    for y,x in zip([0,0,-1,1], [1,-1,0,0]):
        nh,nw = ch+y, cw+x
        if not(0 <= nh < H and 0 <= nw < W):
            continue
        if dist[nh][nw] == None:
            stack.append((nh,nw))
            dist[nh][nw] = dist[ch][cw] + 1
        else:
            dist[nh][nw] = min(dist[nh][nw], dist[ch][cw] + 1)

print(ans)
# print(*dist, sep="\n")


Measured memory_bytes: 124124
Imports System
Module ABC104B
	Function Check(ByVal s As String) As Boolean
		If s(0) <> "A" Then Return False
		
		Dim cnt As Integer = 0
		Dim l As Integer = s.Length
		For idx As Integer = 2 To l-2
			If s(idx) = "C" Then cnt += 1
		Next
		If cnt <> 1
			Return False
		End IF
		
		cnt = 0
		For idx As Integer = 0 To l-1
			If Char.IsUpper(CType(s(idx),Char)) Then cnt += 1
		Next
		If cnt <> 2
			Return False
		End IF
		Return True
	
	End Function
	
	Sub Main()
		Dim s As String = Console.ReadLine()
		
		If Check(s)
			Console.WriteLine("AC")
		Else
			Console.WriteLine("WA")
		End IF
		
	End Sub
End Module



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

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;



ll N = 0;
ll M, D;
ll tmp;
ll ret = 0;

void input() {
  IN(M);
  IN(D);
}

void solve() {
  FOR(i, 1, D+1) {
    ll d1 = i%10;
    ll d2 = i/10;
    ll m = d1 * d2;
    if (1 <= m && m <= M && d1 > 1 && d2 > 1) {
      ret += 1;
    }
  }
  PRINT(ret);
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 256
a=input()
a=int(a)
b=input().split()
b=[int(i) for i in b]
ans=0
b.sort()
if a%2==1:
  print(0)
elif b[a//2]==b[a//2-1]:
  print(0)
else:
  print(b[a//2]-b[a//2-1])


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  int mx = *max_element(A.begin(), A.end());
  int mi = *min_element(A.begin(), A.end());
  cout << mx - mi << "\n";
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String S[] = s.split(" ");
		for(int i = 0 ; i < 3 ; i++) {
			System.out.print(S[i].substring(0, 1));
		}
		System.out.println();
	}
}


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


int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i,n){
    cin >> vec[i];
  }
  set<int> S;
  rep(i,n-1){
    int s = 0, t = 0;
    rep(j,i+1){
      s += vec[j];
    }
    rep(k,n-i-1){
      t += vec[n-1-k];
    }
   
    S.insert(max(s,t) - min(s,t));
  }
  cout << *begin(S);
  
    
  return 0;
}

Measured memory_bytes: 3620
N,M = map(int, input().split())
datas = []
for i in range(M):
  data=list(map(int, input().split()))
  datas.append(data[1:])
p = list(map(int, input().split()))

result = 0
for sw in range(2**N):
  lights = True
  for i,data in enumerate(datas):
    count = 0
    for d in data:
      if sw >> (d-1) & 1 == 1:
        count += 1
        
    if count % 2 != p[i]:
      lights = False

  if lights:
    result += 1
print(result)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    int N; cin >> N; 
    ll ans=-99999999999;
    bool F[110][20]; 
    ll P[110][20];

    rep(i,N){
        rep(j,10){
            cin >> F[i][j];
        }
    }

    rep(i,N){
        rep(j,11){
            cin >> P[i][j];
        }
    }

    for(int i=1; i<(1<<10); i++){
        ll pos=0;
        for(int j=0; j<N; j++){
            int cnt=0;
            for(int t=0; t<10; t++){
               if((i>>t&1) && F[j][t]){
                cnt++;
               }
            }
            pos+=P[j][cnt];
        }
        if(ans<pos)ans=pos; 
    }
    cout << ans << endl;

    return 0;
}


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

constexpr int MAX_N = 2000;

#define USE_DIVISOR
#ifdef USE_DIVISOR
constexpr int DIVISOR = 1e9+7;
#endif

vector<vector<long long>> combination_vec(MAX_N + 1, vector<long long>(MAX_N + 1, 0));
void init_combination() {
  for (int n = 0; n < combination_vec.size(); ++n) {
    combination_vec[n][0] = 1;
    combination_vec[n][n] = 1;
  }
  for (int n = 1; n < combination_vec.size(); ++n) {
    for (int r = 1; r < n; r++) {
      combination_vec[n][r] = (combination_vec[n - 1][r - 1] + combination_vec[n - 1][r]);
#ifdef USE_DIVISOR
      combination_vec[n][r] %= DIVISOR;
#endif
    }
  }
}

template<typename T>
T combination(T n, T r) {
  return combination_vec[n][r];
}

int main() {
  init_combination();

  long long N, K;
  cin >> N >> K;
  long long S{N - K};

  for (long long i{1}; i <= K; ++i) {
    long long ans = combination(S + 1, i);
    ans *= combination(K - 1, i - 1);
    cout << ans % DIVISOR << endl;
  }
}


Measured memory_bytes: 31616
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int A,B;cin>>A>>B;
  
  if(B<A){
    cout<<A-1<<endl;
  }
  else{
    cout<<A<<endl;
  }
}

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

void run(void){
  const int mod=1000000007;
  int h,w;
  scanf("%d%d",&h,&w);
  char *s=(char *)calloc(w+1,sizeof(char));
  int *dp=(int *)calloc(w+1,sizeof(int))+1;
  dp[0]=1;
  while(h--){
    scanf("%s",s);
    for(int i=0;i<w;i++){
      if(s[i]=='#'){
	dp[i]=0;
      } else {
	dp[i]+=dp[i-1];
	if(dp[i]>=mod) dp[i]-=mod;
      }
    }
  }
  printf("%d\n",dp[w-1]);
}

int main(void){
  run();
  return 0;
}


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

int main(){
  int t,n,k,x[100001],L[100],a[100001];
  cin>>t;

  for(int i=0;i<t;i++){
    cin>>n>>k;
    
    for(int j=1;j<n+1;j++){
      cin>>x[j];
    }
    
    for(int j=1;j<n;j++){
      a[j]=x[j+1]-x[j];
    }
    
    sort(a,a + n);
    
    L[i]=x[n]-x[1];
    
    for(int j=1;j<k;j++){
      L[i]-=a[n-j];
    }
    
  }

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

Measured memory_bytes: 1952
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int arr[200010];

int main()
{
	int n,i;
	cin>>n;
	
	for(i=2;i<=n;i++)
		cin>>a[i];
		
	for(i=2;i<=n;i++)
		arr[a[i]]++;
		
	for(i=1;i<=n;i++)
		cout<<arr[i]<<endl;
		
	return 0;
}


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

int main() {
  using pii = pair<int,int>;
  int H, W;
  cin >> H >> W;
  char A[H][W];
  queue<pii> que;
  int d[H][W];
  rep(i, H) {
    rep(j, W) {
      cin >> A[i][j];
      if(A[i][j]=='#') que.push(pii(i,j));
      d[i][j]=0;
    }
  }
  int dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
  int ans=0;
  while(que.size()) {
    pii p=que.front();
    que.pop();
    rep(i,4) {
      int ny=p.first+dy[i], nx=p.second+dx[i];
      if(0<=ny&&ny<H&&0<=nx&&nx<W&&A[ny][nx]=='.'&&d[ny][nx]==0) {
        que.push(pii(ny,nx));
        d[ny][nx]=d[p.first][p.second]+1;
        ans=max(ans, d[ny][nx]);
      }
    }
  }
  cout << ans << endl;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

//a1 左塗りつぶす a2右　a3下　a4 上
//a1,a3 最大値　a2,a4 最小値　a2-a1  a4-a3

int main()
{
    lint w, h, n;
    cin >> w >> h >>n;
    lint a1 = 0, a2 = w, a3 = 0, a4 = h;
    REP(i, n) {
        lint x,y,a;
        cin >> x >> y >> a;
        if (a == 1)
        {
            a1 = max(a1, x);
        }
        if (a == 2)
        {
            a2 = min(a2, x);
        }
        if (a == 3)
        {
            a3 = max(a3, y);
        }
        if (a == 4)
        {
            a4 = min(a4, y);
        }
    }

    lint ans;
    if(a2-a1<=0||a4-a3<=0){
        cout << 0 << "\n";
        return 0;
    }
    ans = (a2 - a1)*(a4 - a3);
    //ans = max(0ll, ans);

    cout<< ans << "\n";

    return 0;
}

Measured memory_bytes: 256
// AOJ DPL_1_G Knapsack Problem with Limitations
// 2018.5.12 bal4u
 
#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
 
int in()
{
    int n = 0, c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

#define MAX_N 102
#define MAX_W 10002

int v[MAX_N], w[MAX_N], m[MAX_N];
int dp[MAX_W];

int main()
{
	int N, W, i, j, k, sw, sv, s, cnt, ans;

	N = in(), W = in();
	for (i = 0; i < N; i++) {
		v[i] = in(), w[i] = in(), m[i] = in();
	}

	for (i = 0; i < N; i++) {
		for (k = 0; m[i] > 0; k++) {
			cnt = 1 << k; // 品物iの個数
			if (cnt > m[i]) cnt = m[i];
			m[i] -= cnt;
			sw = cnt * w[i], sv = cnt * v[i];
			for (j = W; j >= sw; j--) {
				s = dp[j - sw] + sv;
				if (dp[j] < s) dp[j] = s;
			}
		}
	}

	ans = 0;
	for (i = 0; i <= W; i++) {
		if (dp[i] > ans) ans = dp[i];
	}
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 
ll a[2005],dp[2005][2005],b[2005];
bool vis[2005][2005];
ll N;
ll solve(ll idx,ll l,ll r)
{
	if(idx==N+1)
		return 0;
	if(vis[idx][l])
		return dp[idx][l];

	vis[idx][l]=true;
	

	ll left=solve(idx+1,l+1,r)+b[a[idx]]*(a[idx]-l);
	ll right=solve(idx+1,l,r-1)+b[a[idx]]*(r-a[idx]);

	return dp[idx][l]=max(left,right);
}

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;
	vector<pll>v;
	cin >> n;
	N=n;
	for(i=1;i<=n;i++)
	{
		cin >> b[i];
		v.pb(mp(b[i],i));
	}
	sort(all(v));
	reverse(all(v));
	for(i=1;i<=n;i++)
		a[i]=v[i-1].ss;

	cout<<solve(1,1,n)<<endl;
}

Measured memory_bytes: 30444
N, P = map(int, input().split())
S = input()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
    print(ans)
else:
    for i, s in enumerate(S[::-1]):
        a = (a + int(s) * pow(10, i, P)) % P
        ans += C[a]
        C[a] += 1
    print(ans)

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

int main(){
    int N;
    int sum1=0;
    int sum2=0;
    cin>>N;
    vector <int> vec(N);
    for(int i=0;i<N;++i){
        cin >> vec.at(i);
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    for(int i=0;i<N;++i){
        if(i%2==0){
            sum1 += vec.at(i);
        }
        else{
            sum2 += vec.at(i);
        }
    }
    cout << sum1-sum2 <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;++i)
#define mod 1000000007

int main(){
  ll n,a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  string ans="NO";
  ll res1=0,res2=0;
  rep(m,n){
    res1=-d*m+c*(n-1-m);
    res2=-c*m+d*(n-1-m);
    if(res1<=b-a&&b-a<=res2){
      ans="YES";
    }
  }
  cout << ans <<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 100000
#define Q 50000
int main(){
  int n, q, S[N], T[Q], l, m, r, i, C = 0;
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &S[i]);
  }
  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &T[i]);
  }
  for(i = 0; i < q; i++){
    l = 0;
    r = n;
    while(l < r){
      m = (l + r) / 2;
      if(T[i] == S[m]){
	C++;
	break;
      }
      if(T[i] > S[m]) l = m + 1;
      else if(T[i] < S[m]) r = m;      
    }
  }
  
  printf("%d\n", C);
  return 0;  
}

Measured memory_bytes: 1184
def judge(a,b):
    if a+b>=80:
        print("A")
    if 65<=a+b<80:
        print("B")
    if 50<=a+b<65:
        print("C")
    if 30<=a+b<50 and c<50:
        print("D")
    if 30<=a+b<50 and c>=50:
        print("C")
    if a+b<30:
        print("F")

while True:
    a,b,c=map(int, input().split())
    if a==b==c==-1:
        break
    if a==-1 or b==-1:
        print("F")
    if a!=-1 and b!=-1:
        judge(a,b)



Measured memory_bytes: 5600
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<typeinfo>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<vector<ll>> edge;
vector<ll> depth;
vector<ll> high;
vector<ll> parent;
vector<ll> chi;
vector<ll> sib;


void dfs(ll where){
    ll mx=1;
    for(int i=0;i<edge[where].size();i++){
        const ll &to=edge[where][i];
        depth[to]=depth[where]+1;
        dfs(to);
        mx=max(mx,high[to]+1);
    }
    high[where]=mx;
}


int main(){
    ll n;
    cin>>n;
    edge.resize(n);
    parent.resize(n,-1);
    depth.resize(n,0);
    high.resize(n,1);
    chi.resize(n,0);
    sib.resize(n,-1);
    for(int i=0;i<n;i++){
        ll id;
        cin>>id;
        ll l,r;
        cin>>l>>r;
        if(l!=-1){
            edge[id].push_back(l);
            sib[l]=r;
            chi[id]++;
            parent[l]=id;
        }
        if(r!=-1){
            edge[id].push_back(r);
            sib[r]=l;
            chi[id]++;
            parent[r]=id;
        }
    }
    for(int i=0;i<n;i++){
        if(parent[i]==-1){dfs(i); break;}
    }
    for(int i=0;i<n;i++){
        cout<<"node "<<i<<": parent = "<<parent[i]<<", sibling = "<<sib[i]<<", degree = "<<chi[i]<<", depth = "<<depth[i]<<", height = "<<high[i]-1<<", ";
        if(parent[i]==-1){cout<<"root";}
        else if(edge[i].size()==0){cout<<"leaf";}
        else{cout<<"internal node";}
        cout<<endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 3152
fn main() {
    let s = read_line();
    let s = read_num_vec(s, 2);
    let n = s.get(0).unwrap().to_owned();
    let m = s.get(1).unwrap().to_owned();
    let s = read_line();
    let mut a_vec = read_num_vec(s, n as usize);

    a_vec.sort_by(|a, b| b.cmp(a));
    let last = a_vec.get((m - 1) as usize).unwrap().to_owned();
    let mut sum: i64 = 0;
    for a in a_vec {
        sum += a;
    }
    if last >= (sum + 4 * m - 1) / (4 * m) {
        println!("Yes");
    } else {
        println!("No");
    }
}

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

fn read_num_vec(s: String, length: usize) -> Vec<i64> {
    let mut ws = s.split_whitespace();
    let mut result = vec![];
    for _ in 0..length {
        result.push(ws.next().unwrap().parse().unwrap());
    }
    result
}


Measured memory_bytes: 4352
#include<iostream>

using namespace std;

int main() {
	
	int x, y;
	
	while( cin >> x >> y ) {
		
	if( x == 0 && y == 0 )	
	break;
	
	if ( x <= y)	
	cout << x << " " << y << "\n";
	
	else
	cout << y << " " << x << "\n";
		
	}
		
	return 0;
}


Measured memory_bytes: 2992
import java.util.*;


class Main{
	
	
	
	
	public static void main(String[] args){
		
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		
		System.out.print(a*b);
		System.out.print(" ");
		System.out.print((a+b)*2);
		System.out.println("");
		
		
	}
}

Measured memory_bytes: 25936