akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pque priority_queue
#define pi acos(-1)
#define int long long
#define N 1000000
typedef pair < int, int > ii;
typedef pair < int, ii > iii;
typedef vector < int > vi;
const int mod = 1000000007;
int n, m, x, a[2009], b[2009], c[2009], sz[2009];
int pw(int u, int v)
{
	if(v == 0)
		return 1;
	if(v == 1)
		return u;
	int res = pw(u, v / 2);
	res = (res * res) % mod;
	if(v % 2 > 0)
		res = (res * u) % mod;
	return res;
}
int pset(int u)
{
	if(sz[u] < 0)
		return u;
	return u = pset(sz[u]);
}
void join(int u, int v)
{
	u = pset(u);
	v = pset(v);
	if(u == v)
		return;
	if(sz[u] > sz[v])
		swap(u, v);
	sz[u] += sz[v];
	sz[v] = u;
}
int mst()
{
	pque < iii, vector < iii >, greater < iii > > pq;
	int res = 0;
	for(int i = 1; i <= m; i ++)
		pq.push(mp(c[i], mp(a[i], b[i])));
	while(!pq.empty())
	{
		int C = pq.top().fi;
		int A = pq.top().se.fi;
		int B = pq.top().se.se;
		pq.pop();
		if(pset(A) == pset(B))
			continue;
		join(A, B);
		res += C;
	}
	return res;
}
int cal(int val)
{
	//cout << val << endl;
	int A, B, C;
	A = B = C = 0;
	for(int i = 1; i <= m; i ++)
	{
		for(int j = 1; j <= n; j ++)
			sz[j] = - 1;
		join(a[i], b[i]);
		int sum = c[i] + mst();
		if(sum < val)
			A ++;
		else
			B ++;
		//cout << i << ' ' << sum << endl;
	}
	//cout << A << ' ' << B << ' ' << C << endl;
	A = min(A, 1LL);
	return pw(2, A + B);
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> x;
	for(int i = 1; i <= m; i ++)
		cin >> a[i] >> b[i] >> c[i];
	cout << (cal(x) - cal(x + 1) + mod) % mod; 
}



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

int main () {
  int N;
  cin >> N;
  string ans = "No";

  for(int c = 0; 4*c <= N; ++c) {
    for(int d = 0; 7*d <= N-4*c; ++d) {
      if(4*c + 7*d == N) {
        ans = "Yes";
      }
    }
  }
  cout << ans << endl;
}


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

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) (a).begin(),(a).end()

template<typename T1, typename T2> inline void chkmin(T1 & x, const T2 & y) {if (y < x) x = y;}
template<typename T1, typename T2> inline void chkmax(T1 & x, const T2 & y) {if (x < y) x = y;}

#define int ll

int n;

void read() {
	cin >> n;
}

bool getZ(int x, int y, int n) {
	//int l = 0, r = n + 1;
	//while (l < r - 1) {
	//	int z = (l + r) / 2;
	//	if (x * x + y * y + z * z + x * y + x * z + y * z <= n) {
	//		l = z;
	//	} else {
	//		r = z;
	//	}
	//}
	//return x * x + y * y + l * l + x * y + x * l + y * l == n;
	for (int z = 1; x * x + y * y + z * z + x * y + x * z + y * z <= n; z++) {
		if (x * x + y * y + z * z + x * y + x * z + y * z == n) {
			return true;
		}
	}
	return false;
}

int get(int n) {
	ll ans = 0;
	for (int x = 1; x * x <= n; x++) {
		for (int y = 1; x * x + y * y + x * y <= n; y++) {
			if (getZ(x, y, n)) {
				ans++;
			}
		}
	}
	return ans;
}

void run() {
	for (int i = 1; i <= n; i++) {
		cout << get(i) << "\n";
	}
}

void write() {

}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(20), cout.setf(ios::fixed);
	read();
	run();
	write();
	return 0;
}

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

using namespace std;

int n;
vector<char> cstr;
int partCount = 0;

void printStrings(int i) {
	if (i == n) {
		for (char c : cstr) printf("%c", c + 'a');
		printf("\n");
	} else {
		for (int k = 0; k < partCount; ++k) {
			cstr.push_back(k);
			printStrings(i + 1);
			cstr.pop_back();
		}
		cstr.push_back(partCount++);
		printStrings(i + 1);
		cstr.pop_back();
		--partCount;
	}
}

int main() {
	scanf("%d", &n);
	printStrings(0);
	return 0;
}


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

using namespace std;

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

	vector<int> e(n), w(n);
	for (int i = 0; i < n; i++) {
		if (s[i] == 'E') {
			e[i] = 1;
		}
		else {
			w[i] = 1;
		}
	}
	for (int i = 1; i < n; i++) {
		w[i] += w[i - 1];
		e[i] += e[i - 1];
	}

	int mn = e[n - 1];
	int t;
	for (int i = 1; i < n; i++) {
		t = w[i - 1];
		t += e[n - 1] - e[i];
		mn = min(mn, t);
	}
	cout << mn << endl;

	return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define MOD 1000000007
template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

void add(long long &x, long long y){ x = (x + y) % MOD; }
long long dp[100001][101][2];

int main(){
    string K;
    int D;
    cin >> K >> D;
    int N = K.size();
    dp[0][0][0] = 1;
    for(int i=0; i<N; i++){
        int dig = K[i] - '0';
        REP(j, D) REP(k, 10){
            add(dp[i+1][(j+k)%D][1], dp[i][j][1]);
            if(k == dig)
                add(dp[i+1][(j+k)%D][0], dp[i][j][0]);
            if(k < dig)
                add(dp[i+1][(j+k)%D][1], dp[i][j][0]);
        }
    }
    long long ans = (dp[N][0][0] + dp[N][0][1]) % MOD;
    add(ans, MOD-1);
    cout << ans << endl;
    return 0;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  rep(i, n) v[i] = 1;
  rep(i, k){
    int d;
    cin >> d;
    for(int j = 0; j < d; ++j){
      int a;
      cin >> a;
      v[a-1] = 0;
    }
  }
  cout << int(accumulate(v.begin(), v.end(), 0)) << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>   
using namespace std;
#define N 3005   
#define REP(i, n) for(int i=0; i<n; i++)
int n;
int d[N];
int x[N];

int main(){
 scanf("%d",&n);
 REP(i,n)scanf("%d",&d[i]);
 
 REP(i,n){
    if(x[d[i]]==0){
       x[d[i]]=1;
    }
 }
 int ans=0;
 for(int i=1;i<=100;i++){
    if(x[i]==1){
       ans++;
    }
 }
 cout << ans << endl;
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,K,L = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    p,q = list(map(int,input().split()))
    Network1.union(p-1,q-1)
for i in range(L):
    r,s = list(map(int,input().split()))
    Network2.union(r-1,s-1)

dam=[0]*N
D = {}
for i in range(N):
    X = Network1.find(i)
    Y = Network2.find(i)
    dam[i] = str(X) + "_" + str(Y)
    D[str(X) + "_" + str(Y)] = D.get(str(X) + "_" + str(Y), 0) + 1 #なかったら0を返す
out=[]
for i in range(N):
    out.append(D[dam[i]])

print(*out)

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

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int add(int i, int j) {
    if((i += j) >= mod) i -= mod;
    return i;
}

int mult(int i, int j) {
    return (ll) i * j % mod;
}

int A[26];

int main() {
    int n; cin >> n;
    char c;
    while(n--) {
        cin >> c;
        A[c - 'a'] += 1;
    }
    
    int mx = 1;
    
    for(int i = 0; i < 26; ++i)
        mx = mult(mx, A[i] + 1);
    
    cout << mx - 1;
    
    return 0;
}

Measured memory_bytes: 256
function Main (input) {
  input = input.split("\n");
  var N = parseInt(input[0], 10);
  var S = input[1];
  var ans = "Yes";
  if (N%2 == 1) {
    ans = "No";
  }
  else {
    var temp = S.slice(0, N/2);
    if (temp + temp != S) {
      ans = "No";
    }
  }
  console.log(ans);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

const int maxn = 4e3;
int A, B, st[maxn + 3], top;
bool res[maxn + 3];

bool query(int x, int y) {
	static char s[3];
	printf("? %d %d\n", x - 1, y - 1);
	fflush(stdout);
	scanf("%s", s);
	return s[0] == 'Y';
}

int main() {
	scanf("%d %d", &A, &B);
	if (A <= B) {
		puts("Impossible");
	} else {
		for (int i = 1; i <= A + B; i++) {
			if (!top || query(st[top], i)) {
				st[++top] = i;
			} else {
				top--;
			}
		}
		int x = st[top];
		for (int i = 1; i <= A + B; i++) {
			res[i] = query(x, i);
		}
		putchar('!'), putchar(' ');
		for (int i = 1; i <= A + B; i++) {
			putchar('0' + res[i]);
		}
		puts("");
		fflush(stdout);
	}
	return 0;
}

Measured memory_bytes: 724
s = input()
def WA():
  print('WA')
  exit()
if s[0] != 'A':
  WA()
if ord(s[-1]) < ord('a') or ord('z') < ord(s[-1]):
  WA()
if ord(s[1]) < ord('a') or ord('z') < ord(s[1]):
  WA()
s = s[1:]
ccnt = 0
for i in s[1:-1]:
  if i == 'C':
    ccnt += 1
  elif ord(i) < ord('a') or ord('z') < ord(i):
    print('WA')
    exit()
if ccnt != 1:
  print('WA')
  exit()
else:
  print('AC')

Measured memory_bytes: 9168
_ = input()
S = input().lstrip('.').rstrip('#')
n = len(S)

x = 0
y = S.count('.')
c = min(n-y, y)
for i in range(n):
  if S[i] == '#':
    x += 1
  else:
    y -= 1
  c = min(c, x+y)
print(c)

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

using namespace std;

const int N = 2345, mod = 1e9 + 7;

void add(int& x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int mul(int x, int y) {
  return (long long) x * y % mod;
}

int n, k, fac[N * N], ifac[N * N], inv[N * N], dp[N][N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  if (k == 1) {
    cout << 1 << '\n';
    return 0;
  }
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = 1; i <= n * k; ++i) {
    if (i > 1) {
      inv[i] = mul(mod - mod / i, inv[mod % i]);
    }
    fac[i] = mul(fac[i - 1], i);
    ifac[i] = mul(ifac[i - 1], inv[i]);
  }
  auto binom = [&] (int n, int m) {
    return n < 0 || m < 0 || n < m ? 0 : mul(fac[n], mul(ifac[m], ifac[n - m]));
  };
  dp[0][0] = 1;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i + 1 <= n && i + 1 >= j) {
        add(dp[i + 1][j], dp[i][j]);
      }
      if (j + 1 <= n && i >= j + 1) {
        add(dp[i][j + 1], mul(dp[i][j], mul(n - j, binom(n * k - i - j * (k - 1) - 1, k - 2))));
      }
    }
  }
  cout << dp[n][n] << '\n';
  return 0;
}

Measured memory_bytes: 72960
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1e9 + 7

using namespace std;


int main()
{
	int N, K;
	cin >> N >> K;
	vector<int> h(N + K + 100);
	for (int i = 0; i < N; i++)
	{
		cin >> h[i];
	}

	vector<long long int> dp(N + K + 100, INF);
	dp[0] = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j <= K; j++)
		{
			dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
		}
	}

	cout << dp[N - 1] << endl;

	return 0;
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define INF LLONG_MAX/2
#define PI acos(-1.0)
//#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

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;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
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;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int count(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}


void solve(long long X){
    int ans=0;
    ans += (X/500)*1000;
    X %= 500;
    ans += (X/5)*5;
    cout<<ans<<endl;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 256
/*Remember: The Struggle Is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     F            first
#define     S            second

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{	
  	int n;
  	cin>>n;
  	cout<<n*n*n;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NumberOfOnes __builtin_popcount
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twoll pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define y1 y1922
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
typedef
tree<
  int,// aq pair<int,int> shegidzlia
  null_type,
  less/*_equal*/<int>,// aqac
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
// '_equal' mashin ginda roca multiset gchirdeba
template<class key, class value,class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ordered_map<int, int> my_map;
inline int rin(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
int k,n,f[308][308][308];
string s;
int main(){FAST;xRand;
cin>>s;
cin>>k;
n=sz(s);
for(int i=n-1;i>=0;i--){
	for(int j=i;j<n;j++){
		for(int p=0;p<=k;p++){
			if(i==j){
				f[i][j][p]=1;
				continue;
			}
			if(i+1==j){
				f[i][j][p]=(s[i]==s[j]||p>0)?2:1;
				continue;
			}
			f[i][j][p]=max(f[i+1][j][p],f[i][j-1][p]);
			if(s[i]==s[j]){
				f[i][j][p]=max(f[i][j][p],f[i+1][j-1][p]+2);	
			}
			if(p>0){
				f[i][j][p]=max(f[i][j][p],f[i+1][j-1][p-1]+2);
			}
		}
	}
}
cout<<f[0][n-1][k]<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/



Measured memory_bytes: 112896
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n; cin >> n;
    vector<ll> b(n);
    REP(i,n) cin >> b[i];
    bool can = false;
    vector<ll> ans;
    while(true){
        can = false;
        /*if (b.size() == 1) {
            if (b[0] == 1) {
                ans.push_back(b[0]);
                can = true;
                break;
            }
            else {
                can = false;
                break;
            }
        }
        else {*/
            for (int i = b.size()-1; i >= 0; --i) {
                if (i+1 == b[i]) {
                    ans.push_back(b[i]);
                    b.erase(b.begin()+i);
                    can = true;
                    break;
                }
            }
        //}
        if (b.size() == 0) break;
        if (!can) break;
    }
    if (!can) {
        cout << -1 << endl;
        return 0;
    }
    else {
        REPR(i,ans.size()-1) cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n:usize,
        k:usize
    }
    let mut ans = k;
    for i in 0..n - 1 {
        ans *= (k - 1);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<string>
#include<map>
#include<list>

using namespace std;

using llint = long long int ;
using ullint = unsigned long long int;


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

    int n;
    string ans = "No";

    cin >> n;

    for(int a=1; a<=9; a++){
        if(n%a==0){
            if(n/a < 10){
                ans = "Yes";
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n,k = [int(i) for i in input().split()]
all_num = {'0','1','2','3','4','5','6','7','8','9'}
l = all_num - {i for i in input().split()}

for i in range(n,n*20):
    if not set(str(i)) - l:
        print(i)
        break



Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <set>
#include <cassert>
using namespace std;
typedef unsigned long long ll;

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N,0);
    vector<vector<ll>> v(200001);
    for(int i=0;i<N;i++){
        cin >> A[i];
        v[A[i]].push_back(i);
    }
    vector<vector<ll>> ne(N,vector<ll>(60,0)),delta(N,vector<ll>(60,0));
    for(int i=1;i<=200000;i++){
        int n = v[i].size();
        for(int j=0;j<n;j++){
            ne[v[i][j]][0] = (v[i][(j+1)%n]+1)%N;
            delta[v[i][j]][0] = v[i][(j+1)%n]+(j+1==n? N:0)-v[i][j]+1;
        }
    }
    for(int j=1;j<60;j++) for(int i=0;i<N;i++){
        ne[i][j] = ne[ne[i][j-1]][j-1];
        if(delta[i][j-1]+delta[ne[i][j-1]][j-1]<N*K+1) delta[i][j] = delta[i][j-1]+delta[ne[i][j-1]][j-1];
        else delta[i][j] = N*K+1;
    }
    ll id = 0;
    ll res = N*K;
    while(true){
        bool update = false;
        for(int j=59;j>=0;j--){
            if(res>delta[id][j]){
                res -= delta[id][j];
                id = ne[id][j];
                update = true;
                break;
            }
        }
        if(!update) break;
    }
    vector<ll> ans;
    set<ll> s;
    for(int i=id;i<N;i++){
        if(s.empty() || s.count(A[i])==0){
            ans.push_back(A[i]);
            s.insert(A[i]);
        }else{
            while(!ans.empty() && s.count(A[i])==1){
                s.erase(ans.back());
                ans.pop_back();
            }
        }
    }
    for(auto x:ans) cout << x << " ";
    cout << endl;
}


Measured memory_bytes: 228080
import sys

H, W = map(int, input().split())

board = [0 for i in range(H)]
for i in range(H):
    board[i] = list(input())
INF = 100000
dis = [[INF for i in range(H)] for j in range(W)]
queue = []
queue.insert(0, (0, 0))
dis[0][0] = 0
while len(queue):
    x, y = queue.pop()

    if x == W - 1 and y == H - 1:
        count = 0
        for i in range(W):
            for j in range(H):
                if board[j][i] == "#":
                    count += 1
        print(H*W - count - dis[W-1][H-1] -1)
        sys.exit()
        break

    for i in range(0, 4):
        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
        if 0 <= nx < W and 0 <= ny < H and board[ny][nx] != "#":
            if dis[nx][ny] == INF:
                queue.insert(0, (nx, ny))
                dis[nx][ny] = dis[x][y] + 1

print(-1)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
using namespace std;
int main() {
	int count, rcount=0, res=0;
	cin >> count;
	char *arr = new char[count];
	for (int i = 0; i < count; i++) {
		cin >> arr[i];
		if (arr[i] == 'R') rcount++;
	}
	for (int i = 0; i < rcount; i++) {
		if (arr[i] != 'R') res++;
	}
	cout << res;
}

Measured memory_bytes: 3812
import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        if(n>=400 && n<=599){
            System.out.println(8);
        }
        else if(n>=600 && n<=799){
            System.out.println(7);
        }
        else if(n>=800 && n<=999){
            System.out.println(6);
        }
        else if(n>=1000 && n<=1199){
            System.out.println(5);
        }
        else if(n>=1200 && n<=1399){
            System.out.println(4);
        }
        else if(n>=1400 && n<=1599){
            System.out.println(3);
        }
        else if(n>=1600 && n<=1799){
            System.out.println(2);
        }
        else if(n>=1800 && n<=1999){
            System.out.println(1);
        }
    }
}



Measured memory_bytes: 35792
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}


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

int main() {
  int n,m,x;
  cin>>n>>m>>x;
  int v;
  int a=0;
  int b=0;
  for(int i=0;i<m;i++){
    cin>>v;
    if(v<x)a++;
    else b++;
  }
  cout<<min(a,b)<<endl;
}


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

struct _station {
	int elapse;
	int start;
	int interval;
};

int elapse_to_next_station(int now, struct _station station) {
	int start;
	if (now < station.start) {
		start = station.start;
	}
	else {
		if (((now - station.start) % station.interval) == 0) {
			start = now;
		}
		else {
			start = now + station.interval - ((now - station.start) % station.interval);
		}
	}
	//cout << "start:" << start << " -> " << start + station.elapse << endl;
	return start + station.elapse;
}

int main()
{
    int n;
    cin >> n;
	n--;
    struct _station* a = new struct _station[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i].elapse >> a[i].start >> a[i].interval;
    }
    
	for(int i = 0; i < n; i++) {
		int time = 0;
		for (int j = i; j < n; j++) {
			time = elapse_to_next_station(time, a[j]);
		}
		cout << time << endl;
    }
	cout << 0 << endl;
    delete [] a;
    
    return 0;
}


Measured memory_bytes: 888
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>
#include <assert.h>
#include <map>
#include <set>
#include <vector>
#include <functional>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#include <bitset>
// #include <iostream>
// #include <iomanip>
// #include <sstream>
using namespace std;
// const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
// const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
// const int dy[] = {-1, 1, 1, -1, 2, -2, 2, -2};
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define pf printf
#define sf scanf
#define fr(i, a, b) for(int i = a ; i < (int)b ; i++)
#define frr(i, a, b) for(int i = a ; i >= (int)b ; i--)
#define tr(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define trr(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define its(x) static_cast< ostringstream & >( ( ostringstream() << dec << x ) ).str()
#define boost ios_base::sync_with_stdio(false)
#define boost2 cin.tie(NULL)
#define ln puts("")
#define mems(a) memset(a, 0, sizeof(a))
#define has(cont, x) ((cont).find((x)) != (cont).end())
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
ll on_bit(ll x, int pos) {x |= (1ll << pos); return x;}
int off_bit(int x, int pos) {x &= ~(1 << pos); return x;}
bool is_on_bit(ll x, int pos) {return ((x & (1ll << pos)) != 0);}
int flip_bit(int x, int pos) {x ^= (1 << pos); return x;}
int lsb(int x) {return x & (-x);}
int on_bit_all(int x, int pos) {x = (1 << pos)-1; return x;}
const double EPS = 1e-9;
const double PI = 2*acos(0.0);
const int INF = 0x3f3f3f3f;
const ll LLINF = 1e18;
const int MOD = 1e9+7;
int add(ll a, ll b){return ((a%MOD)+(b%MOD))%MOD;}
int sub(ll a, ll b){return ((a%MOD)-(b%MOD))%MOD;}
int mult(ll a, ll b){return ((a%MOD)*(b%MOD))%MOD;}
ll powmod(ll a,ll b){ll res=1;assert(b>=0);a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

int main(){
	int n;
	sf("%d",&n);
	if(n==25)puts("Christmas");
	if(n==24)puts("Christmas Eve");
	if(n==23)puts("Christmas Eve Eve");
	if(n==22)puts("Christmas Eve Eve Eve");
	return 0;
}

Measured memory_bytes: 128
mod=10**9+7
def mull(a,b):
	return ((a%mod)*(b%mod))%mod
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product =mull(product,A[i]) 
        return product 
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product =mull(product,A[j]) 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range(k) : 
  
        # product from left pointers 
        left_product = A[i] * A[i + 1] 
  
        # product from right pointers 
        right_product = A[j] * A[j - 1] 
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product =mull(product,left_product) 
            i += 2
          
        else : 
            product=mull(product,right_product) 
            j -= 2
  
    # Finally return product 
    return product 
def check(a):
	for i in a:
		if i>=0:
			return False 
	return True 
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
mod=10**9+7
ans=1 
if check(a):
	if k%2==0:
		a.sort()
		for i in a[:k]:
			ans=mull(ans,i+mod)  
	else:
		a.sort(reverse=True)
		for i in a[:k]: 
			ans=mull(ans,i+mod) 
	print(ans%mod)
else:
	print(maxProductSubarrayOfSizeK(a,n,k)%mod)


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  if(A == 7 && B == 5 && C == 5) cout << "YES" << endl;
  else if(A == 5 && B == 7 && C == 5) cout << "YES" << endl;
  else if(A == 5 && B == 5 && C == 7) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1<<30;

int main(){
  string s;cin>>s;
  bool ans=false;
  for(int i=0;i<(int)s.size()-1;i++){
    if(s.substr(i, 2)=="AC"){ans=true;break;}
  }
  cout<<(ans?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], b[N], dp[1 << 12];
int main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int k, A, t = 0; scanf("%d%d", &a[i], &k);
		for (int j = 1; j <= k; j++) scanf("%d", &A), t |= 1 << (A - 1);
		b[i] = t;
	}
	memset(dp, 0x3f, sizeof(dp)), dp[0] = 0;
	for (int i = 1; i <= m; i++) 
		for (int j = 0; j < 1 << n; j++) if (dp[j] < 1e9)
			dp[j | b[i]] = min(dp[j | b[i]], dp[j] + a[i]);
	int res = dp[(1 << n) - 1];
	if (res < 1e9) cout << res << endl;
	else puts("-1");
}

Measured memory_bytes: 256
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

ans = []

for i in range(2 ** n):
    jud = [0]*m
    money = 0
    for j in range(n):
        if (i >> j) & 1:
            money += ca[j][0]
            for k in range(m):
                jud[k] += ca[j][k+1]
    if min(jud) >= x:
        ans.append(money)

if not ans:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 9216
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N, M, R;
	static int[] x, y, z, r;
	static long[] l;

	public static void main(String[] args) {
		while (true) {
			N = sc.nextInt();
			M = sc.nextInt();
			if (N == 0) break;
			System.out.println(solve());
		}
	}

	static int solve() {
		final int INF = 1 << 28;
		int[][] dl = new int[N][N];
		int[][] ds = new int[N][N];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				dl[i][j] = ds[i][j] = INF;
			}
			dl[i][i] = ds[i][i] = 0;
		}
		for (int i = 0; i < M; ++i) {
			int X = Integer.parseInt(sc.next()) - 1;
			int Y = Integer.parseInt(sc.next()) - 1;
			int T = Integer.parseInt(sc.next());
			boolean land = sc.next().charAt(0) == 'L';
			if (land) {
				dl[X][Y] = dl[Y][X] = Math.min(dl[X][Y], T);
			} else {
				ds[X][Y] = ds[Y][X] = Math.min(ds[X][Y], T);
			}
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					dl[j][k] = Math.min(dl[j][k], dl[j][i] + dl[i][k]);
					ds[j][k] = Math.min(ds[j][k], ds[j][i] + ds[i][k]);
				}
			}
		}
		R = sc.nextInt();
		int PZ = sc.nextInt() - 1;
		int[][] dp = new int[2][N];
		Arrays.fill(dp[0], INF);
		Arrays.fill(dp[1], INF);
		dp[0][PZ] = 0;
		int t = 1;
		for (int i = 1; i < R; ++i) {
			int Z = sc.nextInt() - 1;
			Arrays.fill(dp[t], INF);
			for (int j = 0; j < N; ++j) {
				if (dp[t ^ 1][j] == INF) continue;
				for (int k = 0; k < N; ++k) {
					dp[t][k] = Math.min(dp[t][k], dp[t ^ 1][j] + dl[PZ][j] + ds[j][k] + dl[k][Z]);
				}
				dp[t][j] = Math.min(dp[t][j], dp[t ^ 1][j] + dl[PZ][Z]);
			}
			t ^= 1;
			PZ = Z;
		}
		int ans = INF;
		for (int i = 0; i < N; ++i) {
			ans = Math.min(ans, dp[t ^ 1][i]);
		}
		return ans;
	}

}

Measured memory_bytes: 65608
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// Linear sieve that additionally precalculates some common multiplicative functions
struct Sieve {
	vector<int> primes;  // primes[i]    := i+1'th prime
	vector<int> div_ind; // div_ind[x]   := minimum i s.t. primes[i] \divides x
	vector<int> mobius;  // mobius[p^k]  := [k == 0] - [k == 1]

	Sieve(int n) : div_ind(n+1, -1), mobius(n+1, 1) {
		vector<int> base(n+1, 1);
		for (int i = 2; i <= n; ++i) {
			if (div_ind[i] == -1) {
				div_ind[i] = primes.size();
				primes.push_back(i);
			}
			for (int j = 0; j <= div_ind[i]; ++j) {
				int p = primes[j];
				int t = p * i;
				if (t > n) break;
				div_ind[t] = j;
				base[t] = (j == div_ind[i] ? base[i] : i);
			}

			// Calculate multiplicative functions
			int bs = base[i];
			if (bs == 1) {
				int p = primes[div_ind[i]];
				int j = i/p;
				mobius[i]  = (i == p ? -1 : 0);
			} else {
				int pk = i/bs;
				mobius[i]  = mobius[bs]  * mobius[pk];
			}
		}
	}
};

ll modInv(ll a, ll b = MOD - 2) {
	if (b & 1) return a * modInv(a, b-1) % MOD;
	if (b == 0) return 1;
	return modInv(a*a % MOD, b / 2);
}

const int N = 1 + (int)1e6;
ll mdi[N];
ll cou[N];
ll sum[N];
ll aux[N];

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

	for (int i = 1; i < N; ++i) mdi[i] = modInv(i);
	Sieve sv(N);

	for (int t = 1; t < N; ++t) {
		for (int m = 1; m*t < N; ++m) aux[t*m] += mdi[t] * sv.mobius[m];
		aux[t] %= MOD;
		if (aux[t] < 0) aux[t] += MOD;
	}

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		++cou[a];
	}
	for (int t = 1; t < N; ++t) {
		for (int r = t; r < N; r += t) sum[t] += (ll)cou[r] * r;
		sum[t] %= MOD;
	}

	ll res = 0;
	for (int t = 1; t < N; ++t) {
		ll mult = (sum[t] * sum[t]) % MOD;
		res += (aux[t] * mult) % MOD;
	}
	for (int d = 1; d < N; ++d) {
		res -= (ll)cou[d] * d % MOD;
	}
	res = ((res%MOD) * mdi[2]) % MOD;
	if (res < 0) res += MOD;
	cout << res << '\n';

	// \sum_{a} \sum_{b} lca(a, b);
	// = \sum_{a} \sum_{b} ab / gcd(a, b)
	// = \sum_{a} \sum_{b} \sum_{k} [gcd(a, b) == k] ab / k
	// = \sum_{k} 1/k \sum_{a} \sum_{b} ab [gcd(a, b) == k]
	// = \sum_{k} 1/k \sum_{a} \sum_{b} ab \sum_{d | gcd(a, b)/k} mob(d)
	// = \sum_{k} \sum_{d} 1/k mob(d) \sum_{dk | a} \sum_{dk | b} ab
	// = \sum_{t} (\sum_{k | t} 1/k mob(t/k)) (\sum_{t | a} a)^2
	// = \sum_{t} aux[t] sum[t]
}








Measured memory_bytes: 39732
#include <bits/stdc++.h>
typedef long long int ll;
#define pb push_back
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define MOD 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
using namespace std;

int main() {
  ll n, c, k;
  cin >> n >> c >> k;
  vector<ll> v;
  REP(i, n) {
    ll h;
    cin >> h;
    v.pb(h);
  }
  sort(v.begin(), v.end());
  ll cnt = 0, last = v[0], p = 0;
  for (auto &a : v) {
    cerr << p << " " << last << endl;
    if (a - last > k || p == c) {
      cnt++;
      last = a;
      p = 0;
    }
    p++;
  }
  cout << cnt + 1 << endl;
}


Measured memory_bytes: 1400
<?php
// https://atcoder.jp/contests/abc045/tasks/abc045_a
// 台形の面積を求める

// fgets(STDIN)で標準入力,trimで改行を削除
$a = trim(fgets(STDIN));
$b = trim(fgets(STDIN));
$h = trim(fgets(STDIN));

echo ($a + $b)/2 * $h."\n";

Measured memory_bytes: 4728
#include<bits/stdc++.h>
using namespace std;
int n,k;
int main() {
	cin>>n>>k;
	if (k>(1<<n)-1) puts("-1");
	else if (n==1) {
		if (k==0) puts("0 0 1 1\n");
		else puts("-1");
	}
	else {
		cout<<k<<' ';
		for (int i=0;i<=(1<<n)-1;++i) {
			if (i!=k) cout<<i<<' ';
		}
		cout<<k<<' ';
		for (int i=(1<<n)-1;i>=0;--i) {
			if (i!=k) cout<<i<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ll n, w;
	cin >> n >> w;
 
	ll wts[n + 1];
	ll vals[n + 1];
	ll max_val = 0;
	for (int i = 1; i <= n; i++)
	{	cin >> wts[i];
		cin >> vals[i];
		max_val += vals[i];
	}
 
 
	ll dp[n + 1][max_val + 1];
 
 
 
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= max_val; j++)
		{
			dp[i][j] = INT_MAX;
		}
	}
 
	for (int i = 0; i <= n; i++)
		dp[i][0] = 0;
 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= max_val; j++)
		{
			if (j - vals[i] >= 0)
				dp[i][j] = min(dp[i - 1][j - vals[i]] + wts[i], dp[i - 1][j] );
			else
				dp[i][j] = dp[i - 1][j];
		}
	}
 
	int ans = 0;
 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= max_val; j++)
		{
			if (dp[i][j] <= w)
				ans = max(ans, j);
		}
	}
	cout << ans << endl;
 
}
 
 


Measured memory_bytes: 82308
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=1e9;
int main(void)
{
    int N,A[100005];
    cin >> N;
    vector<pair<int,int> > p(N);
    for(int i=0;i<N;i++)
    {
        cin >> A[i];
        p[i]=pii(A[i],i+1);
    }
    sort(p.begin(),p.end());
    for(int i=0;i<N;i++)
    {
        if(i!=N-1) cout << p[i].second << ' ';
        else cout << p[i].second << endl;
    }
    return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
int a=0,b=0;
char c;
string s;
signed main()
{
	cin>>s;
	rep(i,s.size()){
		if(s[i]!='A'&&s[i]!='T'&&s[i]!='C'&&s[i]!='G'){
			b=0;
		}else{
			b++;
			if(a<b){
				a=b;
			}
		}
	}
	cout<<a;
}

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

using namespace std;

#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000000
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
  int n, m, q;
  cin >> n >> m >> q;
  int a[n][n];
  REP(i, n)REP(j, n) a[i][j] = 0;
  REP(i, m){
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    a[l][r]++;
  }
  REP(i, n) REP(j, n-1) a[n-2-j][i] += a[n-1-j][i];
  REP(i, n-1) REP(j, n) a[j][i+1] += a[j][i];
  REP(i, q){
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << a[l][r] << endl;
  }
	return 0;
}


Measured memory_bytes: 1920
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n=sc.nextLong(),k=sc.nextLong();
		HashMap<Long,Long> hm=new HashMap<Long,Long>();
		long[] h=new long[(int)n];
		long ite=0;
		for(int i=0;i<n;i++){
			long a=sc.nextLong();
			long buf=sc.nextLong();
			if(hm.containsKey(a)){
				hm.put(a, hm.get(a)+buf);
			//	System.out.println(a+" "+hm.get(a));
			}else{
				h[(int)ite]=a;
			//	System.out.println("h["+ite+"]="+h[ite]);
				ite++;
				hm.put(a, buf);
			//	System.out.println(a+" "+hm.get(a));
			}
		}
		for(int z=0;z<n;z++){
		//	System.out.print(h[z]+" ");
		}
		Arrays.sort(h);
		for(int z=0;z<n;z++){
		//	System.out.print(h[z]+" ");
		}
		int i=0;
		while(h[i]==0){
		//	System.out.println("h["+i+"]="+h[i]);
			i++;
		}
		while(k>0&&i<n){
		//	System.out.println(i);
			k-=hm.get(h[i]);
			i++;
		//	System.out.println(k);
		}
		System.out.println(h[--i]);
	}
}


Measured memory_bytes: 94628
function Main(input) {
  var input = input.split('\n');

  var ballXList = input[2].split(' ');
  var ret = 0;
  for (var i = 0; i < input[0]; i++) {
    var aDistance = ballXList[i];
    var bDistance = input[1] - ballXList[i];
    var ret = ret + (aDistance < bDistance ? aDistance : bDistance) * 2;
  }

  console.log(ret);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
using ll = long long;

using namespace std;
int main(){
	string S;
	ll allsum= 0;
	cin >> S;
	int len = S.size();
	for (int tmp = 0; tmp < (1 << len); tmp++) {
		bitset<9>bit(tmp);
		string cutstr = S;
		rep(i, len-1) {
			if (bit.test(i)) {
				allsum += stoll(cutstr.substr(len - 1 - i));
				cutstr.erase(len - 1 - i);
			}
		}
		allsum += stoll(cutstr);
	}
	cout << allsum/2 << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

bool all_reachable(const std::vector<std::vector<int> >& adjacencies, int start_idx, int end_index) {
    std::vector<bool> visited(adjacencies.size(), false);
    std::queue<int> queue;
    queue.push(start_idx);
    while (!queue.empty()) {
        int node_idx = queue.front();
        queue.pop();
        visited[node_idx] = true;

        for (int neighbour_idx : adjacencies[node_idx]) {
            if (!visited[neighbour_idx]) {
                queue.push(neighbour_idx);
            }
        }
    }
    return visited[end_index];
}

void cut_edge(VVI& adj, int start_idx, int end_index){
  for(auto it = begin(adj[start_idx]); it!=end(adj[start_idx]); ++it){
    if(end_index == *it){
      adj[start_idx].erase(it);
      break;
    }
  }
  for(vector<int>::iterator it = adj[end_index].begin(); it!=adj[end_index].end(); ++it){
    if(*it == start_idx){
      adj[end_index].erase(it);
      return;
    }
  }
}

void dispGraph(VVI& adj){
  for(auto i : adj){
    for(auto j : i){
        cout << j << " ";
    }
    cout << "\n";
  }
}

int main(void){
  int a,b;
  cin>>a>>b;
  int cnt = b-a;
  int s = 0;
  for(int i=1; i<= cnt-1; i++){
    s+= i;
  }
  cout<<s-a<<endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

INF = float('inf')

vec1 = [[INF] * N for _ in range(N)]
vec2 = [[INF] * N for _ in range(N)]

for _ in range(M) :
    a, b, c = map(int, input().split())
    vec1[a-1][b-1] = vec1[b-1][a-1] = vec2[a-1][b-1] = vec2[b-1][a-1] = c
    
for i in range(N) :
    vec1[i][i] = vec2[i][i] = 0
    
for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            vec1[i][j] = min(vec1[i][j], vec1[i][k] + vec1[k][j])

ret = 0            
for i in range(N) :
    for j in range(i+1, N) :
        if vec2[i][j] != INF and vec1[i][j] != vec2[i][j] :
            ret += 1

print(ret)

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

typedef pair<int, int> ii;

int main() {
    int n, m; cin >> n >> m;
    ii students[n];
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        students[i] = make_pair(a, b);
    }
    ii checkpoints[m];
    for (int i = 0; i < m; i++) {
        int c, d; cin >> c >> d;
        checkpoints[i] = make_pair(c, d);
    }

    for (int i = 0; i < n; i++) {
        int index = 0;
        int a = students[i].first, b = students[i].second;
        int min_d = 1e9;
        for (int j = 0; j < m; j++) {
            int c = checkpoints[j].first, d = checkpoints[j].second;
            int distance = abs(a - c) + abs(b - d);
            if (distance < min_d) {
                index = j + 1;
                min_d = distance;
            }
        }
        cout << index << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  string S, T, U;
  int A, B;
  cin >> S >> T >> A >> B >> U;
  if (S == U)
  {
    A--;
  }
  else
  {
    B--;
  }
  cout << A << " " << B << endl;
}

Measured memory_bytes: 3588