akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<int,int>;
using Graph=vector<vector<int>>;
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();}
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;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
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(){
  ll L,R,D;
  cin>>L>>R>>D;
  co(R/D-(L-1)/D);
  return 0;
}

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

int main() {
	int n, l;
	cin >> n >> l;
	vector<string> ss;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		ss.push_back(s);
	}
	sort(ss.begin(), ss.end());
	for (auto s : ss) {
		cout << s;
	}
	cout << endl;
	return 0;
}

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

#define int long long
#define fi first
#define se second
#define ponto pair<int,int>

int n,x, v[300000];

int32_t main()
{
	cin >> n;
	
	for(int i=1; i<n; i++)
	{
		cin >> x;
		v[x]++;
	}
	
	for(int i=1; i<=n; i++)
		cout << v[i] << '\n';
}

Measured memory_bytes: 5132
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef tuple<int, int, int, int> t4;
typedef pair<ll, ll> PL;
typedef long double ldouble;

string A[10010];
string X;

void solve(){
	int n; cin >> n;
	rep(i, n)cin >> A[i];
	cin >> X;
	int l = 0, r = 0;
	rep(i, n){
		string p = A[i];
		for(auto &e : p)if(e == '?')e = 'a';
		if(p <= X)++r;
		p = A[i];
		for(auto &e : p)if(e == '?')e = 'z';
		if(p < X)++l;
	}
	for(int i=l;i<=r;i++){printf("%d", i+1); if(i < r)printf(" "); } puts("");
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include<math.h>
using namespace std;
int main() {
 long long int a,b,n,h;
  long long int arr[100000] ;
  cin>> h ;
  arr[1]=h;
  n=1;
  a=0;
  b=1;
  while(arr[n]!=1){
    n++;
    arr[n]=arr[n-1]/2 ;
    
    b=b*2;
  }
 
  a=pow(2,n-1);
  cout<<a+b-1;

}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

void check(string s, int sx, int sy, int tx, int ty)
{
  int n = s.size();
  int x = sx, y = sy;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'U') { ++y; }
    else if (s[i] == 'D') { --y; }
    else if (s[i] == 'L') { --x; }
    else if (s[i] == 'R') { ++x; }

    if (x == sx and y == sy) {
      fprintf(stderr, "DEBUG: got to (sx, sy)\n");
    }
    else if (x == tx and y == ty) {
      fprintf(stderr, "DEBUG: got to (tx, ty)\n");
    }
  }
}

int main()
{
  int sx, sy, tx, ty; scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
  int dx = tx - sx, dy = ty - sy;
  string ans = string(dx, 'R') + string(dy, 'U') + string(dx, 'L') + string(dy, 'D');
  ans += string(1, 'D') + string(dx + 1, 'R') + string(1 + dy, 'U') + string(1, 'L');
  ans += string(1, 'U') + string(dx + 1, 'L') + string(1 + dy, 'D') + string(1, 'R');
  // check(ans, sx, sy, tx, ty);
  printf("%s\n", ans.c_str());
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

const long long INFL = 1e17+7;
const long long INFI = 1e9+7;
const long long MOD = 1e9+7;
const double EPS = 1e-8;
const double PI=acos(-1);

using namespace std;


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int x;
    cin >> x;
    int ans=10-x/200;
    cout << ans << endl;
  
	return 0;
}


Measured memory_bytes: 3612
#!/usr/bin/env python3
#AGC14 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
cnt = [0]*n
for _ in range(m):
    a,b = LI()
    cnt[a-1] += 1
    cnt[b-1] += 1
for i in range(n):
    if cnt[i] % 2:
        print('NO')
        quit()
print('YES')


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

int main() {
    int A,B,C;
    cin >> A >> B >> C;
    if((A-C)*(B-C)>0){
        cout << "No" << endl;
    }else
    {
        cout << "Yes" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
#include <string>
#include <cmath>

using namespace std;

int main(int argc, char const *argv[]) {
    string S;
    cin >> S;
    bool keys[3] = {false, false, true};
    if (S[0] == 'A') keys[0] = true;

    int cnt = 0;
    for (int i = 2; i < S.length()-1; i++){
        if (S[i] == 'C') {
            cnt++;
        }
    }
    if (cnt == 1) keys[1] = true;

    for (int i = 1; i < S.length(); i++){
        if ('A' <= S[i] && S[i] <= 'Z'){
            if (S[i] == 'C' && 2 <= i && i < S.length()-1) continue;
            keys[2] = false;
        }
    }

    if (keys[0] && keys[1] && keys[2]){
        cout << "AC" << endl;
    } else {
        cout << "WA" << endl;
    }

    return 0;
}


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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}


int main()
{
	int S=0,W=0;
	scanf("%d %d", &S,&W);

	if(W<S){
		printf("safe");
	}
	
	else{
		printf("unsafe");
	}

	return 0;
}


Measured memory_bytes: 1704
#include <bits/stdc++.h>
#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using namespace std;
signed main (){
  vector<char> a(3);
  bool answer = false ;
  rep(i,3){
    cin>>a[i];
    if(a[i]=='7'){
      answer = true;
    }
  }
  if(answer){
    cout<<"Yes"<<endl;
  }
  else if(!answer){
    cout<<"No"<<endl;
  }
}

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

int n, m, k, s, ans = 0;
vector<int> needs[11];
vector<int> p(11);

bool check(string key)
{
	for (int i = 0; i < m; i++)
	{
		int amount = 0;

		for (auto each : needs[i])
			if (key[each] == '1')
				amount++;

		if (amount % 2 != p[i])
			return false;
	}

	return true;
}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> k;

		for (int j = 0; j < k; j++)
		{
			cin >> s;
			needs[i].push_back(s - 1);
		}
	}

	for (int i = 0; i < m; i++)
		cin >> p[i];

	for (int mask = 0; mask < (1 << n); mask++)
	{
		string key = "0000000000";

		for (int i = 0; i < n; i++)
			key[i] = char(((mask >> i) & 1) + '0');

		if (check(key))
			ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int a, b, c, d ;
	double e;
	scanf("%d%d", &a, &b);
	c = a / b;
	d = a%b;
	e = (double)a / b;
	printf("%d %d %f",c, d, e);
	return 0;
}

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

#define th 3.141592653589793/3

struct point {
	double x, y;
};

void print(point p) {
	cout << fixed << setprecision(8) << p.x << " " << p.y << endl;
}

void koch(int d, point p1, point p2) {
	if (d == 0)
		return;
	point s, u, t;
	s.x = (2 * p1.x + p2.x) / 3;
	s.y = (2 * p1.y + p2.y) / 3;
	t.x = (p1.x + 2 * p2.x) / 3;
	t.y = (p1.y + 2 * p2.y) / 3;
	u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
	u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;
	koch(d - 1, p1, s);
	print(s);
	koch(d - 1, s, u);
	print(u);
	koch(d - 1, u, t);
	print(t);
	koch(d - 1, t, p2);
}

int main() {
	int n;
	cin >> n;
	point a, b;
	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;
	print(a);
	koch(n, a, b);
	print(b);
	return 0;
}



Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define inf 2001001001
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
#define F first
#define S second
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
using priority_queue_small = priority_queue<int, vector<int>, greater<int> >;
template<class T>using vv = vector<T>;
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; }
template<class T>void show(const vector<T> &a) { for (int i = 0; i < (int)a.size(); ++i) cout << a[i] << (i != (int)a.size()-1 ? " " : "\n"); }
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
int dy[]={0, 1, -1, 0};
int dx[]={1, 0, 0, -1};

int n, m;
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
  cin >> n >> m;
  vii a(n), b(n), c(m), d(m);
  rep(i, 0, n) cin >> a[i] >> b[i];
  rep(i, 0, m) cin >> c[i] >> d[i];
  rep(i, 0, n) {
    int dist = inf, idx = 0;
    rep(j, 0, m) {
      int t = abs(a[i] - c[j]) + abs(b[i] - d[j]);
      if (dist > t) {
        idx = j;
        dist = t;
      }
    }
    cout << idx + 1 << endl;
  }
  return 0;
}



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

int main() {
 
  string s1;
  int ans=0;
  cin >> s1 ;
  if(s1[0]=='1') ans++;
  if(s1[1]=='1') ans++;
  if(s1[2]=='1') ans++;
  cout << ans << endl;
}


Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion



int main(void) {
  ll a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  if (a + b < 2 * c) {
	ans = a * x + b * y;
  }
  else {
	if (x > y) {
	  ans += y * 2 * c;
	  if (a < 2 * c) {
		ans += llabs(x - y)*a;
	  }
	  else {
		ans += llabs(x - y)*c * 2;
	  }
	}
	else {
	  ans += x * 2 * c;
	  if (b < 2 * c) {
		ans += llabs(x - y)*b;
	  }
	  else {
		ans += llabs(x - y)*c * 2;
	  }
	}
  }
  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define int long long
main()
{
    int m, n, k, a, b, c, d;
    cin >> n;
    vector<int> v(n);
    bool can = 0;
    for( int i = 0; i < n; i++ ) cin >> v[i];
    sort( begin(v), end(v) );
    int pre;
    for( int x : v )if(  x < v[n/2] ) pre = x;
    int dist1 = lower_bound( begin(v), end(v), v[n/2] ) - begin(v), dist2 = end(v) - lower_bound( begin(v), end(v), v[n/2] );
    if(dist1 == dist2 )
    {
        cout << v[n/2] - pre<< endl;;        
    }
    else puts("0");
    return 0;
}

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

int main() {
    long long K;
    cin >> K;
    
    long long N = 50;
    cout << N << endl;
    for(int i=0; i<N; ++i) {
        cout << (i - (K % N) + N + 1) % (N + 1) + (K / N) << (i + 1 == N ? '\n' : ' ');
    }    
}

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


using namespace std;


typedef long long LL;
typedef pair<LL,LL> pp;

int main()
{
	int N;
	
	cin >> N;
	
	if (N%10 == N/100) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	cout << endl;
	exit(0);
}



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

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i) // ROF(i,n,0)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで降順
#define SUM(a) accumulate(all(a),int(0))
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>T add(const T &a, const T &b){return (a+b)%mod;}

struct node{
  ll v, d;
  node(ll _v, ll _d):v(_v),d(_d){}
  bool operator<(const node &n) const { return d > n.d; }
};
struct edge{
  ll from, to, d;
  edge(ll _from, ll _to, ll _d):from(_from),to(_to),d(_d){}
};
class bellmanford{
public:
  ll n,m;
  vector<edge> G;
  vector<ll> dist;
  vector<ll> nega;
  vector<ll> prev;

  bellmanford(ll s, ll _n, vector<edge> &_G):n(_n),G(_G){ // s:始点
    m = G.size();
    dist.resize(n,inf);
    prev.resize(n,-1);
    dist[s] = 0;
    
    rep(i, n-1) rep(j, m){
      ll u = G[j].from, v = G[j].to, c = G[j].d;
      if(dist[u] != inf and dist[v] > dist[u] + c){
	dist[v] = dist[u] + c;
	prev[v] = u;
      }
    }      
  }
  
  void negative(){ // sからtへの経路中に負閉路があればnega[t] = true
    nega.resize(n,0);
    rep(i, n) rep(j, m){
      ll u = G[j].from, v = G[j].to, c = G[j].d;
      if(dist[v] != inf and dist[v] > dist[u] + c){
	dist[v] = dist[u] + c;
	nega[v] = true;
      }
      if(nega[u]) nega[v] = true;
    }
  }
};


signed main(){
  int n, m, p; cin >> n >> m >> p;
  vector<edge> g;
  rep(i,m){
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    g.push_back(edge(a,b,-c+p));
  }
  bellmanford bf(0,n,g);
  bf.negative();
  if(bf.nega[n-1]){
    cout << -1 << endl;
  }else{
    cout << -min(0ll,bf.dist[n-1]) << endl;
  }
}


Measured memory_bytes: 576
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, A[int(1e5 + 5)];

int main(){
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d", A + i);
  sort(A, A + N);

  if (A[N - 1] - A[0] > 1){
    No(); return 0;
  }

  int C = A[0], D = A[0] + 1, K = 0;
  for (int i = 0; i < N; i++){
    if (A[i] == C) K++;
  }


  if (K < N && K <= C && C + 1 <= K + (N - K) / 2) Yes();
  else if (K == N && (C <= N / 2 || C == N - 1)) Yes();
  else No();

  return 0;
}


Measured memory_bytes: 4084
N = list(input())
counter = 0
for i in range(9) :
    if N[0] == N[1] == N[2] :
        counter += 1
if counter == 0 :
    for j in range(10) :
        if N[1] == N[2] == N[3] :
            counter += 1
if counter == 0 :
    print("No")
else :
    print("Yes")
    
    

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

int compare(const void *a,const void *b){
  return *(int *)a - *(int *)b;
}

int main(){
  int n;
  int a[200000];
  int b[200000];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    b[i] = a[i];
  }
  qsort(b,n,sizeof(int),compare);
  int max = b[n-1];
  int next = b[n-2];
  for(int i=0;i<n;i++){
    if(a[i] != max){
      printf("%d\n",max);
    }else{
      printf("%d\n",next);
    }
  }
  return 0;
}

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

static const int MAX = 200000;

int main() {
  int a,b;
  cin >> a >> b;
  std::vector<bool> vec(3,true);
  vec.at(a-1) = false;
  vec.at(b-1) = false;
  for (int i = 0; i < 3; i++) {
    if (vec.at(i)) cout << i+1 << endl;
  }

}


Measured memory_bytes: 3476
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=998244353;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e9;
const long double PI=acos(-1);

int n,m;
int a[1003],b[1003];
int msk[6000];

int memo[1003][5000];
int mx;

int dp(int idx,int msk1){
    if(idx==m){
        if(msk1==mx){
            return 0;
        }
        return 1e9;
    }
    if(memo[idx][msk1]!=-1)return memo[idx][msk1];
    int tmp=msk1 | msk[idx];
    int ch1=dp(idx+1,tmp)+a[idx];
    int ch2=dp(idx+1,msk1);
    return memo[idx][msk1]=min(ch1,ch2);
}

void solve(int T){
    memset(memo,-1,sizeof(memo));
    //cout<<memo[10][10]<<"\n";
    cin>>n>>m;
    mx=((1<<n)-1);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        for(int j=0;j<b[i];j++){
            int x;
            cin>>x;
            msk[i]|=(1<<(x-1));
        }
    }
    int ans=dp(0,0);
    cout<<((ans!=1e9)?ans:-1)<<"\n";
}

int main() {
    //fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 23268
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

def p(arr):
	print("_______________________")
	for i in arr:
		for j in i:
			print(j,end=" ")
		print()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = [["#" for i in range(w+2)]]+[["#"]+ list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]

q = deque()
visited = [[-1]*(w+2) for i in range(h+2)]
count = (w+2)*(h+2)
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]=="#":
			visited[i][j] = float("inf")
			count -= 1

from pprint import pprint
visited[ch][cw] = 0

q = {(ch,cw)}
set_list = set()
cost = 0
while count:
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		count-=1
		if s[x-1][y]=="." and visited[x-1][y]==-1:
			q.add((x-1,y))
		if s[x][y-1]=="." and visited[x][y-1]==-1:
			q.add((x,y-1))
		if s[x+1][y]=="." and visited[x+1][y]==-1:
			q.add((x+1,y))
		if s[x][y+1]=="." and visited[x][y+1]==-1:
			q.add((x,y+1))

	if len(set_list)==0:
		break

	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for dx in range(-2,3):
			for dy in range(-2,3):
				x2 = x+dx
				y2 = y+dy
				if visited[min(x2,h+1)][min(y2,w+1)]!=-1: continue
				q.add((x2,y2))

print(visited[dh][dw])

Measured memory_bytes: 139224
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	int ans=(b-1)/(a-1);
	if((b-1)%(a-1))
	{
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
arr=[]
STDIN.each{|l|
  l=l.split(' ')
  l.each{|e|
    case e
    when '+'
      arr.push arr.pop + arr.pop
    when '-'
      arr.push -arr.pop +  arr.pop
    when '*'
      arr.push arr.pop * arr.pop
    when '/'
      arr.push 1 / arr.pop * arr.pop
    else
      arr.push e.to_f
    end

  }
  puts '%.6f' %[arr.pop]
}

Measured memory_bytes: 6132
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <stack>

using namespace std;
int main(int argc, const char * argv[]) {
    
    
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d);

    for (int i=0; i<d; i++){
        cin >> p[i] >> c[i];
    }

    int ans = __INT_MAX__;
    for (int mask=0; mask < (1<<d); mask++) {
        int s = 0, cnt = 0, rm=-1;
        for(int i=0; i<d; i++) {
            if (1&(mask>>i)){
                s += p[i]*(i+1)*100+c[i];
                cnt += p[i];
            } 
            else {
                rm = i;
            }
        }

        if (s<g) {
            int r=g-s+(rm+1)*100-1;
            int rr = r/((rm+1)*100);
            if (rr >= p[rm]){
                continue;
            }
            cnt += rr;
        }

        ans = min(ans, cnt);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    int ans = inf;
    int n = S.length();
    rep(i, 0, n - 2) {
        int x = (S[i] - '0') * 100 + (S[i + 1] - '0') * 10 + S[i + 2] - '0';
        chmin(ans, abs(x - 753));
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,m,ans;
int f[N],bz[N];
int find(int bb){
	if (f[bb]!=bb) f[bb]=find(f[bb]);
	return f[bb];
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) f[i]=i;
	int x,y,r1,r2;
	for (int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		r1=find(x),r2=find(y);
		if (r1!=r2)
			f[r2]=r1;
	}
	for (int i=1;i<=n;++i){
		r1=find(i);
		bz[r1]++;
		if (bz[r1]>ans) ans=bz[r1];
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 3220
def calc_gcd(x, y):
    """
    math.gcd()????????¨??§????????????python3.5??\??????AOJ???python?????????????????????3.4????????§?????¨??§?????????
    """
    if y == 0:
        return x
    else:
        return calc_gcd(y, x % y)


if __name__ == '__main__':
    data = [int(x) for x in input().split(' ')]
    result = calc_gcd(data[0], data[1])
    print('{0}'.format(result))

Measured memory_bytes: 7704
def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()

Measured memory_bytes: 9408
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<60;
double pi=3.141592653589793238462643383279L;
double eps=1e-9;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll k,n;cin>>n>>k;
    vector<pll> w;
    ll ma[n+1];
    fill(ma,ma+n+1,-inf);
    rep(i,0,n){
        ll t,d;cin>>t>>d;
        Max(ma[t],d);
        w.push_back({d,t});
    }
    ll sum=0;
    deque<ppll> dq;
    bool used[n+1];
    fill(used,used+n+1,false);
    sort(w.begin(),w.end(),greater<pll>());
    ll syu=0;
    rep(i,0,k){
        
        sum+=w[i].first;
        if(used[w[i].second]==false){
            syu++;
            dq.push_back({w[i],1});
        }
        else dq.push_back({w[i],0});
        used[w[i].second]=true;
    }
    //cout<<sum<<" "<<syu<<endl;
    priority_queue<ll> q;
    rep(i,1,n+1){
        if(used[i]==false&&ma[i]>=0){
            q.push(ma[i]);
        }
    }
    //cout<<sum<<" "<<syu<<" "<<q.size()<<" "<<endl;
    ll ans=sum+syu*syu;
    for(;;){
        if(q.size()==0)break;
        int y=0;
        while(dq.size()>0){
            ppll p=dq.back();dq.pop_back();
            if(p.second==1)continue;
            sum-=p.first.first;
            y=1;
            break;
        }
        if(y==0)break;
        ll r=q.top();q.pop();
        syu++;
        sum+=r;
       // cout<<sum<<endl;
        Max(ans,sum+syu*syu);
    }
    cout<<ans<<endl;
}










Measured memory_bytes: 5104
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

ll gcd(ll x,ll y){
    if(x<y)swap(x,y);
    if(x%y==0)return y;
    return gcd(y,x%y);
}

int main(){
    int n;cin>>n;
    ++n;
    int a[n];
    rep(i,n)cin>>a[i];
    sort(a,a+n);
    int ans=abs(a[1]-a[0]);
    rep(i,n-2)ans=gcd(ans,a[i+2]-a[i+1]);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>

using namespace std;

const int MOD = 1000000007;
typedef long long ll;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int r,g,b,n;
  ll ans=0ll;
  cin>>r>>g>>b>>n;
  for(int i=0;i<=3000;i++){
    for(int j=0;j<=3000;j++){
      if(n-r*i-g*j>=0 && (n-r*i-g*j)%b==0)ans++;
    }
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		String S = sc.next();

		sc.close();

		if (S.charAt(2) == S.charAt(3) && S.charAt(4) == S.charAt(5)) {
			out.println("Yes");
		} else {
			out.println("No");
		}

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

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

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int n;

char init[3] = "SW";
char ans[100010];
char   s[100010];

char another(char s){
  if(s=='S') return 'W';
  return 'S';
}

char flip_s(char s){
  if(s=='o') return 'x';
  return 'o';
}


int main(){
  scanf("%d",&n);
  scanf("%s",s);
  s[n] = s[0];
  s[n+1] = s[1];
  char now,prev;
  REP(i1,2)REP(i2,2){
    prev = init[i1];
    now = init[i2];
    ans[0] = prev;
    ans[1] = now;
    char tmp;
    FOR(i,1,n+2){
      char q = s[i];
      if(now == 'W') q = flip_s(q);
      if(q == 'o'){
        ans[i+1] = ans[i-1];
      }else{
        ans[i+1]= another(ans[i-1]);
      }
      now = ans[i+1];
      prev = ans[i];
    }
    //printf("%s %c\n",ans,tmp);
    if(ans[0] == ans[n] && ans[1] == ans[n+1]){
      ans[n] = '\0';
      printf("%s\n",ans);
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N,c=0,a=1;
  cin>>N;
  while(1){
    if(N==1)break;
    N/=2;
    c++;
  }
  for(int i=0;i<c;i++)a*=2;
  cout<<a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...) 0
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> bl, rd;
    rep(i, 0, n) {
        int a, b;
        cin >> a >> b;
        rd.emplace_back(b, a);
    }
    rep(i, 0, n) {
        int c, d;
        cin >> c >> d;
        bl.emplace_back(c, d);
    }
    sort(bl.begin(), bl.end());
    sort(rd.rbegin(), rd.rend());
    rep(i, 0, n) rd[i] = {rd[i].second, rd[i].first};
    int ans = 0;
    set<int> st;
    debug(bl);
    debug(rd);
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (rd[j].first < bl[i].first && rd[j].second < bl[i].second && st.count(j) == 0) {
                ans++;
                st.insert(j);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

ll mod = 1000000007;


int main() {
	long long x; cin >> x;
	int cnt = 0;
	long long money = 100;
	while(money < x){
		long long tmp = money /100;
		money += tmp;
		cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f(i,x,n) for(int i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
const int MOD = 1e9 + 7, N = 5e5 + 10;
const int LINF = LLONG_MAX;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,v,b,w,t;
    cin >> a >> v >> b >> w >> t;
   	if(a >= b){
   		int r1 = a-v*t;
   		int r2 = b -w*t;
   		if(r1 <= r2){
   			cout << "YES\n";
   		}
   		else
   			cout << "NO\n";
   	}
   	else{
   		int r1 = a+v*t;
   		int r2 = b +w*t;
   		if(r1 >= r2){
   			cout << "YES\n";
   		}
   		else
   			cout << "NO\n";	
   	}
    return 0;
}
 

Measured memory_bytes: 3652
/*author:revolIA*/
/*明日を変えるなら今日変えなきゃ*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e4+7;
int vis[1007],Next[maxn][10],Last[10];
int n,ans;
char Str[maxn];
int main(){
    for(int i=0;i<10;i++)Last[i] = -1;
    scanf("%d%s",&n,Str+1);
    for(int i=n;~i;i--){
        memcpy(Next[i],Last,sizeof Last);
        if(i)Last[Str[i]-'0'] = i;
    }
    for(int i=0;i<1000;i++){
        int x = Next[0][i/100];
        if(x == -1)continue;
        int y = Next[x][i/10%10];
        if(y == -1)continue;
        int z = Next[y][i%10];
        if(z == -1)continue;
        if(vis[i])continue;
        vis[i] = 1;
        //printf("%d\n",i);
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

using T = tuple<ll,ll>;
using Graph = vector<vector<T>>;

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

    ll k, a, b;
    cin >> k;
    cin >> a >> b;

    if (a == b)
    {
        if (a%k==0) cout << "OK" << endl;
        else cout << "NG" << endl;
        return 0;
    }

    for (ll i=1; i<=1000; i++)
    {
        if (i%k==0 && (a<=i && i<=b))
        {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;

    return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <climits>
#include <set>

#define ll long long

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a,b;
    cin>>a>>b;
    int k=0;
    for(int i=0;i<3;i++)
    {
        if(a[i]==b[i])
            k++;
    }
    cout<<k<<'\n';
}










Measured memory_bytes: 3644
#include <iostream>

using namespace std;

using ll = long long;

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()

typedef pair<int, int> P;

const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;

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

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

const int nmax = 40, abmax = 10, inf = 1e6;

int a[nmax], b[nmax], c[nmax];
int dp[nmax + 1][nmax * abmax + 1][nmax * abmax + 1];

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, ma, mb;
	cin >> n >> ma >> mb;
	REP(i, n) cin >> a[i] >> b[i] >> c[i];
	
	REP(i, n + 1) {
		REP(ca, nmax * abmax + 1) {
			REP(cb, nmax * abmax + 1) {
				dp[i][ca][cb] = inf;
			}
		}
	}
	
	dp[0][0][0] = 0;
	
	REP(i, n) {
		REP(ca, nmax * abmax + 1) {
			REP(cb, nmax * abmax + 1) {
				if (dp[i][ca][cb] == inf) continue;
				dp[i + 1][ca][cb] = min(dp[i + 1][ca][cb], dp[i][ca][cb]);
				dp[i + 1][ca + a[i]][cb + b[i]] = min(dp[i + 1][ca + a[i]][cb + b[i]], dp[i][ca][cb] + c[i]);
			}
		}
	}
	
	int ans = inf;
	FOR(ca, 1, nmax * abmax + 1) {
		FOR(cb, 1, nmax * abmax + 1) {
			if (ca * mb == cb * ma) ans = min(ans, dp[n][ca][cb]);
		}
	}
	
	if (ans == inf) ans = -1;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 25984
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double X = Math.floor(N/1.08);

		while(Math.floor((int)X*1.08)<=N){
			if(Math.floor((int)X*1.08)==N){
				System.out.println((int)X);
				return;
			}else{
				X++;
			}
		}
		System.out.println(":(");
    }
}


Measured memory_bytes: 35704
#include <bits/stdc++.h>
using namespace std;
int n;
vector<double> p;
vector<vector<double>> dp;

int main() {
    cin >> n;
    p = vector<double>(n, 0.0);
    for(int i = 0; i < n; ++i) cin >> p.at(i);
    dp = vector<vector<double>>(n+1, vector<double>(n+1, 0.0));
    dp[0][0] = 1.0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < i+1; ++j) {
            if(j == 0) {
                dp[i][j] = dp[i-1][j]*(1.0-p.at(i-1));
            }else {
                dp[i][j] = dp[i-1][j]*(1.0-p.at(i-1)) + dp[i-1][j-1]*p.at(i-1);
            }
        }
    }

    double ans = 0.0;
    /*for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            printf("%.10f ", dp[i][j]);
        }
        cout << endl;
    }*/

    for(int j = n/2+1; j <= n; ++j) {
        ans += dp[n][j];
    }
    printf("%.14f\n", ans);
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=1e9+7;
const int size=1e5+1;
const int inf=1e9;
int N,M,Q;
int A[50],B[50],C[50],D[50];
int ans = 0;
void dfs(int n, vector<int> vec){
	if(n == N){//print(vec,,N);
		int res = 0;
		rep(i,0,Q){
			if(vec[B[i]] - vec[A[i]] == C[i]) res += D[i];
		}ans= max(ans, res);
		return;
	}
	rep(i,vec.back(),M+1){
		vec.push_back(i);
		dfs(n+1, vec);
        vec.pop_back();
	}
	return;
}
int main(){
	cin>>N>>M>>Q;
	rep(i,0,Q){ cin>>A[i]>>B[i]>>C[i]>>D[i]; }
	vector<int> v; v.push_back(1);
	dfs(0, v);
	cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<math.h>
#include<chrono>
#include<list>
#include<random>
#include<bitset>
#include<assert.h>
#include<ctime>
#include<cstdio>
#include <unordered_map>

using namespace std;

#define fast_input() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); }
//#define ll long long
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
MIKUNO - 15/02/1999
*/
const int N = 1e5 + 5;
//	priority_queue <ll, vector<ll>, greater<ll> > q;
//int n, m, k, cnt, rs, q;

int main()
{
	fast_input();
	int n, W;
	cin >> n >> W;
	
	vector<ll>dp(n * 1000 + 1, 1e18);
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		int w, v;
		cin >> w >> v;
		for (int val = n*1000 - v; val >= 0; --val) {
			dp[val + v] = min(dp[val + v], dp[val] + w);
		}
	}
	int ans = 0;
	for (int i = 0; i <= 1000 * n; i++) {
		if (dp[i] <= W) {
			ans = max(ans, i);
		}
	}
	cout << ans;
}

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

namespace HABIT{
    #define f(a,b,c,d) for(register int a=b,c=d;a<=c;a++)
    #define g(a,b,c,d) for(register int a=b,c=d;a>=c;a--)
    #define LOCAL
    typedef int i32;
    typedef unsigned int u32;
    typedef long long int i64;
    typedef unsigned long long int u64;
    const i32 MAXN=1024;
    typedef i32 ar[MAXN];
    
    template<typename T> inline T Max(T a) { return a; }
    template<typename T,typename... Args> inline T Max(T a,Args... args){
        T b=Max(args...);
        return (a>b)?a:b;
    }
    template<typename T> inline T Min(T a) { return a; }
    template<typename T,typename... Args> inline T Min(T a,Args... args){
        T b=Min(args...);
        return (a<b)?a:b;
    }

    #ifdef LOCAL
        inline char gc() { return getchar(); }
    #else
        inline char gc() {
            static char s[1<<20|1]={0},*p1=s,*p2=s;
            return (p1==p2)&&(p2=(p1=s)+fread(s,1,1<<20,stdin),p1==p2)?EOF:*(p1++);
        }
    #endif
    inline i64 read(){
        register i64 ans=0;register char c=gc();register bool neg=0;
        while(c<48||c>57) neg^=!(c^'-'),c=gc();
        while(c>=48&&c<=57) ans=(ans<<3)+(ans<<1)+(c^48),c=gc();
        return neg?-ans:ans;
    }

    char Output_Ans[1<<20|1],*Output_Cur=Output_Ans;
    inline void output() { Output_Cur-=fwrite(Output_Ans,1,Output_Cur-Output_Ans,stdout); }
    inline void print(char c){
        if(Output_Cur-Output_Ans+1>>20) output();
        *(Output_Cur++)=c;
    }
    inline void print(char *s) { while(*s) print( *(s++) ); }
    inline void print(u64 x){
        if(!x) { print('0'); return ; }
        char buf[30]={0},*p=buf+28;
        while(x) *(p--)=x%10+48,x/=10;
        print(p+1);
    }
    inline void print(u32 x) { print( (u64)x ); }
    inline void print(i64 x){
        if(x<0) print('-'),x=-x;
        print( (u64)x );
    }
    inline void print(i32 x){
        if(x<0) print('-'),x=-x;
        print( (u64)x );
    }
}
using namespace HABIT;

inline char *ans(i32 n){
    while(n)
        if(n%10==7) return "Yes";
        else n/=10;
    return "No";
}

int main(){
    print( ans(read()) );
    output();
    return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> l(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    int ans = 0;
    for (int i = 0; i < 2 * n; i += 2) {
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# input
N, M, Q = map(int, input().split())
train_query = {} # 対象区間とクエリを一緒にソート
for i in range(M + Q):
    train_query[i] = list(map(int, input().split()))

train_query = sorted(train_query.items(), key=lambda x: x[1][1])
# 辞書をソートするとリストが返ってくることに注意

StartPoints = [0 for _ in range(N)] # 対象区間の開始位置
ans = [0 for _ in range(Q)] # 各クエリに対する答え

for j in range(M + Q):
    if train_query[j][0] < M: # 対象区間
        StartPoints[train_query[j][1][0] - 1] += 1
    else: # クエリ
        ans[train_query[j][0] - M] = sum(StartPoints[(train_query[j][1][0] - 1):(train_query[j][1][1])])

for i in range(Q):
    print(ans[i])


Measured memory_bytes: 111944
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

int n;
map <string, int> cnt;
int mx = 0;
vector <string> ans;

int main() { 

  scanf("%d\n", &n);
  for (int i = 0; i < n; i++) {
    string s;
    getline(cin, s);
    cnt[s]++;
    mx = max(mx, cnt[s]);
  }

  for (auto p : cnt) {
    if (p.second == mx) {
      ans.push_back(p.first);
    }
  }

  sort(all(ans));

  for (auto s : ans) {
    cout << s << endl;
  }

  return 0;
}


Measured memory_bytes: 27248
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<functional>
#include<bits/stdc++.h>
#include<map>
#include<utility>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;
#define vec2c vector<vector<char>>
#define vec2i vector<vector<int>>
#define vecc vector<char>
#define vecs vector<string>
#define veci vector<int>
#define vecd vector<double>
#define vecl vector<long>
#define vecll vector<long long>
#define rep(i, n) for(int i=0; i < (int)(n); i++)
#define rrep(i, n) for(int i=(int)(n); i>=0;i--)
#define rep1e(i, n) for(int i=1; i <= (int)(n); i++)
#define rep1ne(i, n) for(int i=1; i < (int)(n); i++)
#define pqi priority_queue<int>
#define pqll priority_queue<ll>
#define pqi_ priority_queue<int, vector<int>, greater<int>>
#define pqll_ priority_queue<ll, vector<ll>, greater<ll>>

#define MAX 100010

using namespace std;

unsigned digit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

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

bool isPrime(int num) {
  if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0) return false;
    }
    return true;
}

map<ll,int> prime_factor(ll n) {
  map<ll,int> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

ull gdc(ull a, ull b) {
  if(a < b) return gdc(b, a);
  ull r;
  while((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

  int ans = prime_factor(gdc(A, B)).size() + 1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from math import sqrt, log2, floor
MAX_X = 1000
ALL_EXPONENTIAL = [
    b**p
    for b in range(1, floor(sqrt(MAX_X)) + 1)
    for p in range(2, floor(log2(MAX_X)) + 1)]

X = int(input())
assert 1 <= X <= MAX_X
print(max(filter(lambda candidate: candidate <= X, ALL_EXPONENTIAL)))


Measured memory_bytes: 2940
from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
M = int(input())
T = Counter([input() for _ in range(M)])
n = 0
for s, s_c in S.items():
    t_c = 0 if s not in T else T[s]
    n = max(n, s_c - t_c)
print(n)


Measured memory_bytes: 3316