akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,k,n) for (int i = (k); i < (n); ++i)
#define debug_v(v,N) for(int i=0;i<N;i++) { cout << v[i] << " "; } cout << endl;
using namespace std;
typedef long long ll;

#define MAX_N 100010
// 素数を格納
bool prime[MAX_N];
// 添字が素数か否か
bool is_prime[MAX_N];

// 素数の数を返す
int sieve(int n)
{
    int p = 0;
    for (int i = 0; i <= n; ++i) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;
            for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
        }
    }
    return p;
}

void Main()
{
	int Q; cin >> Q;
	int N = 100000;
	vector<int> l(Q);
	vector<int> r(Q);
	vector<int> S(N + 1, 0);
	rep(i, Q) cin >> l[i] >> r[i];
	int p = sieve(N);
	S[0] = 0;
	REP(i, 0, N) {
		if (is_prime[i + 1] && is_prime[(i + 1 + 1) / 2]) S[i + 1] = S[i] + 1;
		else S[i + 1] = S[i];
	}
	rep(i,Q) {
		cout << (S[r[i]] - S[l[i] - 1]) << endl;
	}
}

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


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

int A[22], B[22], C[22];

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

    int N;
    cin >> N;

    for(int i=1; i<=N; i++)
        cin >> A[i];
    
    for(int i=1; i<=N; i++)
        cin >> B[i];
    
    for(int i=1; i<=N-1; i++)
        cin >> C[i];
    
    int ans = 0;

    for(int i=1; i<=N; i++)
    {
        if(A[i] == A[i-1] + 1)
            ans += C[ A[i-1] ];
        
        ans += B[i];
    }

    cout << ans << "\n";
    return 0;
}


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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

int main()
{
    int k,cnt=0;

    cin>>k;

    int p = 0;
    for(int i=1;i<=2*k;i++)
    {
        p = (p*10+7)%k;
        cnt++;

        if( !p )
        {
            cout<<cnt<<endl;
            return 0;
        }
    }

    cout<<-1<<endl;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll r;
    cin >> r;
    cout << 3 * r * r << endl;
    return 0;
}


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

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

int main(){
	long long a, b;
	cin>>a>>b;
	long long c=gcd(a, b);
	long long ans=a*b;
	ans=ans/c;
	cout<<ans<<endl; 
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int no =-1;
		while(true){
			int m=sc.nextInt();
			int f=sc.nextInt();
			int r=sc.nextInt();
		if(m>=0||f>=0||r>=0) {
		if((m+f)>=80) {
			System.out.println("A");
		}else if(65<=(m+f)&&(m+f)<80) {
			System.out.println("B");
		}else if(r>=50||50<=(m+f)&&(m+f)<65) {
			System.out.println("C");
		}else if(m==-1||f==-1||(m+f)<30) {
			System.out.println("F");
		}else if(30<=(m+f)&&(m+f)<50||r>=50) {
			System.out.println("D");
		}else {
			System.out.println("F");
		}
		}else if(m==-1&&f==-1){
			break;
		}
	}
	}
}





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

int main() {
    int N, M;
    cin >> N >> M;
    int homework = 0;
    for (int i = 0; i < M; i++) {
        int A;
        cin >> A;
        homework += A;
    }
    if (homework > N) cout << -1 << endl;
    else cout << N - homework << endl;
}

Measured memory_bytes: 3632
//-----by LY02------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//------------------------------------------------

int dp[3010][3010];

//------------------------------------------------
int main() {
//------------------------------------------------
//	freopen("In.txt","r",stdin);
//	freopen("Out.txt","w",stdout);
//------------------------------------------------
	ios::sync_with_stdio(0);
	cin.tie(0);
//------------------------------------------------

string s,t; cin>>s>>t;
int zs=s.size(),zt=t.size();
for(int i=1;i<=zs;i++)
{
	for(int j=1;j<=zt;j++)
	{
		dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
		if(s[i-1]==t[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
	}
}
int i=zs,j=zt;
string ans="";
while(i && j)
{
	int a=dp[i-1][j],b=dp[i][j-1],c=dp[i][j];
	if(c>a && c>b)
	{
		ans+=s[i-1];
		i--; j--;
	}
	else if(a>b) i--;
	else j--;
}
reverse(ans.begin(),ans.end());

cout<<ans<<endl;


//------------------------------------------------
	return 0;
}





//-----by LY02------------------------------------


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std ;
template < class R > inline void Readin( R &K ) {
	K = 0 ; bool F = false ; char C = getchar() ; while( C < '0' or C > '9' ) { if( C == '-' ) F = true ; C = getchar() ; }
	while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ; if( F ) K = -K ;
}
template < class R > inline void Checkmax( R &A , R B ) {
	if( A < B ) A = B ;
}
template < class R > inline void Checkmin( R &A , R B ) {
	if( A > B ) A = B ;
}
long long N , X , Ans ;
void Dfs( long long A , long long B ) {
	Ans += ( A / B ) * B * 2ll ;
	if( A % B ) Dfs( B , A % B ) ;
		else Ans -= B ;
}
int main() {
	Readin( N ) ;
	Readin( X ) ;
	Ans = N ;
	Dfs( X , N - X ) ;
	return not printf( "%lld\n" , Ans ) ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,int> P;
main(){
  int n;
  P p[100000],j[100000];
  while(1){
    long long pcnt=0;
    long long maxs=-1;
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++){
      cin>>p[i].first;
      p[i].second=i;
      pcnt+=p[i].first;
    }
    for(int i=0;i<n-1;i++){
      cin>>j[i].first;
      j[i].second=i;
    }
    sort(j,j+n-1);
    for(int i=n;i>0;i--){
      maxs=max(maxs,pcnt*i);
      if(i!=1){
	pcnt+=j[i-2].first;
      }
    }
    cout<<maxs<<endl;
  }
}

Measured memory_bytes: 4292
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;
using namespace std;

typedef long long int lli;
#define int lli
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef vector<pii> vii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OrderedSet;

const int MOD	= 1e9 + 7;
const double PI = acos(-1.0);

#define fastio			ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto &i : c)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define fill(a)  memset(a, 0, sizeof (a))
#define error(x) cerr << #x << " = " << (x) << endl
#define errorp(p) cerr << #p << " = " << (p.first) << ", " << (p.second) << endl

template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }
int mul(int a, int b, int c){lli res=(lli)a*b;return (int)(res>=c?res%c:res);}
template<typename T>T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
int mod_neg(int a, int b, int c){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}

bool comparator(pii a, pii b){
 
    return (a.second - a.first) > (b.second - b.first);
}

signed main(){
    #ifdef DEBUG
		freopen("test", "r", stdin);
	#endif
    fastio;
    
    int N;
    cin >> N;
    vii cnt(N, pii(0, 0));
    vii mid;
    int right = 0, left = 0;

    rep(i, N){
        string s;
        cin >> s;
        int count = 0;
        tr(s, c){
            if(c == '('){
                count++;
            }else{
                count--;
            }
            if(count < 0){
                cnt[i].first++;
                count = 0;
            }
        }
        cnt[i].second = count;
        if(cnt[i].first == 0){
            right += cnt[i].second;
        }else if(cnt[i].second == 0){
            left += cnt[i].first;
        }else{
            mid.eb(cnt[i]);
        }
    }

    sort(all(mid), comparator);

    int curr = right;

    tr(mid, p){
        curr -= p.first;
        if(curr < 0){
            cout << "No" << endl;
            return 0;
        }
        curr += p.second;
    }
    curr -= left;
    if(curr == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 18776
#include <cstdio>
#include <iostream>

using namespace std;

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

  long long n, m, d;
  cin >> n >> m >> d;

  const long long denom = d == 0 ? (m - 1) * n : (m - 1) * 2 * (n - d);
  printf("%.10lf\n", denom * 1.0 / n / n);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int N,M;
int A[100005];
int p[3];
int main()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>A[i];
        if(A[i]%2==1)
        {
            p[0]++;
            if(p[0]>2){cout<<"Impossible";return 0;}
            p[p[0]]=i;
        }
    }
    if(p[1])swap(A[1],A[p[1]]);
    if(p[2])swap(A[M],A[p[2]]);
    for(int i=1;i<=M;i++)cout<<A[i]<<" ";cout<<"\n";
    if(M==1)
    {
        if(A[1]==1)cout<<"1\n1";
        else cout<<"2\n"<<A[1]-1<<" "<<1;
        return 0;
    }
    cout<<M-(A[1]==1)<<"\n";
    for(int i=1;i<=M;i++)
    {
        if(i==1&&A[i]==1)continue;
        cout<<A[i]-(i==1)+(i==M)<<" ";
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

vector<vector<int>> g;
vector<int> d;
vector<int> tr;
vector<int> sz;

void dfs(int cur, int pre, int dst) {
  tr[cur] = pre;
  d[cur] = dst;
  sz[cur] = 1;
  for (auto&& w : g[cur]) {
    if (w != pre) {
      dfs(w, cur, dst + 1);
      sz[cur] += sz[w];
    }
  }
}

void add_edge(int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
}

int main() {
  int n;
  cin >> n;
  g.resize(n);
  d.resize(n, inf);
  sz.resize(n, 1);
  tr.resize(n, inf);

  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    add_edge(a, b);
  }
  dfs(0, -1, 0);
  int t = (d[n - 1]-1) / 2;
  int rt = n - 1;
  for (int i = 0; i < t; i++) rt = tr[rt];

  string ans = ((n - sz[rt] > sz[rt]) ? "Fennec" : "Snuke");
  cout << ans << endl;
//  cerr << rt << " " << sz[rt] << endl;
//  for (auto&& w : sz) cerr << sz[w] << " ";
}


Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	i64 t1, t2, a1, a2, b1, b2;
	scanf("%lld%lld%lld%lld%lld%lld", &t1, &t2, &a1, &a2, &b1, &b2);

	i64 X = t1 * a1 + t2 * a2;
	i64 Y = t1 * b1 + t2 * b2;
	if(!(X < Y)) {
		std::swap(a1, b1);
		std::swap(a2, b2);
		std::swap(X, Y);
	}
	i64 A1 = t1 * a1, A2 = t2 * a2;
	i64 B1 = t1 * b1, B2 = t2 * b2;
	i64 Z = Y - X;

	if(X == Y) {
		printf("infinity\n");
		return 0;
	}
	
	if(A1 < B1) {
		printf("0\n");
		return 0;
	}

	i64 t = (A1 - B1) / Z;
	i64 D = A1 - B1 - t * Z;
	i64 ans = (A1 - B1) / Z * 2 + !!D;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
bool solve(){
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a<b){
    return false;
  }
  if(d<b){
    return false;
  }
  if(b<=c+1){
    return true;
  }
  ll g=GCD(b,d);
  //gで割ってa%gあまり数でb未満になる最大の数
  ll ch=(b-a%g+g-1)/g*g-(g-a%g);
  return ch<=c;
}
int main(){
  int t;
  cin>>t;
  while(t--){
    cout<<(solve()?"Yes":"No")<<"\n";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rrep(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s,t; cin >> s >> t;
  cout << t << s;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

vector<string> split(const string &s,char c=' '){
    vector<string> ret;
    stringstream ss(s);
    string t;
    while(getline(ss,t,c)){
        ret.push_back(t);
    }
    return ret;
}

bool dp[16020], tmp[16020];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int x, y;
    cin >> s >> x >> y;
    vector<string> t = split(s, 'T');
    vector<int> a, b;
    rep(i, 0, t.size()){
        if(i % 2 == 0) a.push_back(t[i].size());
        else b.push_back(t[i].size());
    }
    dp[8010 + a[0]] = true;
    rep(i, 1, a.size()){
        rep(j, 0, 16020) tmp[j] = false;
        rep(j, 0, 16020){
            if(dp[j]){
                tmp[j - a[i]] = true;
                tmp[j + a[i]] = true;
            }
        }
        swap(dp, tmp);
    }
    bool ans = dp[8010 + x];
    rep(i, 0, 16020) dp[i] = false;
    dp[8010] = true;
    rep(i, 0, b.size()){
        rep(j, 0, 16020) tmp[j] = false;
        rep(j, 0, 16020){
            if(dp[j]){
                tmp[j - b[i]] = true;
                tmp[j + b[i]] = true;
            }
        }
        swap(dp, tmp);
    }
    ans &= dp[8010 + y];
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<pair<int,int> >n;
  long long int a,b,c=0;
  int ai,bi;
  cin>>a>>b;
  for(int i=0;i<a;i++){
    cin>>ai>>bi;
    n.push_back(make_pair(ai,bi));
  }

  sort(n.begin(),n.end());
  while(b>0){
    b=b-n[c].second;
    c++;
  }
  cout<<n[c-1].first<<endl;
  return 0;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
    ll n;cin>>n;
    vector<ll>a(n);
    cin>>a[0];
    ll sum=a[0];
    rep(i,n-1){
        ll b;
        cin>>b;
        sum+=b;
        a[i+1]=a[i]+b;
    }
    ll mi=abs(a[0]-(sum-a[0]));
    REP(i,1,n-1){
        mi=min(abs(a[i]-(sum-a[i])),mi);
    }
    cout<<mi<<endl;
}

Measured memory_bytes: 1792
N = int(input())
S = {}
for i in range(N):
    s = ''.join(sorted(input()))
    if s in S.keys():
        S[s] += 1
    else:
        S[s] = 1
ans = 0
for k in S.values():
    if k != 1:
        ans += k * (k - 1) // 2
print(ans)


Measured memory_bytes: 17852
#include "bits/stdc++.h"
using namespace std;

int main(void) {
    long long K, A, B;
    cin >> K >> A >> B;

    if (A >= B - 2) {
        cout << K + 1 << endl;
        return 0;
    }
    long long incl = B - A;
    long long bis = 1;
    long long rest = K;
    while (rest > 0) {
        if (bis >= A && rest >= 2) {
            rest -= 2;
            bis += incl;
            continue;
        }
        ++bis;
        --rest;
    }
    cout << bis << endl;
    return 0;
}

Measured memory_bytes: 256
x = map(int, raw_input().split(' '))
a = tuple(x[:2])
b = tuple(x[2:])
vector = [-(b[1] - a[1]), (b[0] - a[0]) ]

c = [b[0] + vector[0],b[1] + vector[1] ]
d = [a[0] + vector[0],a[1] + vector[1] ]  

print c[0],c[1], d[0],d[1]

Measured memory_bytes: 85576
#include<stdio.h>

int
main(int argc, char *argv[])
{
  int a, b, c, d;
  scanf("%1d%1d%1d%1d", &a, &b, &c, &d);
  if((a==b && b== c) || (b == c && c == d))
  {
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = 1e9+7;

int main(){
	int H, N;
	cin >> H >> N;
	vector<int> A(N), B(N);
	for(int i=0;i<N;i++) cin >> A[i] >> B[i];
	vector<int> dp(H+5,INF);
	dp[H] = 0;
	for(int i=H;i>=0;i--) {
		for(int j=0;j<N;j++) {
			if(i >= A[j]) dp[i-A[j]] = min(dp[i-A[j]], dp[i] + B[j]);
			else if(i < A[j]) dp[0] = min(dp[0], dp[i] + B[j]);
		}
	}
	cout << dp[0] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>

using namespace std;

int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  vector<string> svec;
  map<char,int> mp;
  vector<char> march = {'M', 'A', 'R', 'C', 'H'};
  sort(march.begin(), march.end());
  for (size_t i = 0; i < n; i++) {
    string s;
    cin >> s;
    svec.push_back(s);
    if (find(march.begin(), march.end(), s[0]) != march.end()) mp[s[0]]++;
  }
  vector<long long int> nums;
  for(auto x : mp){
    nums.push_back(x.second);
  }
  if (nums.size() < 3) cout << 0 << endl;
  else {
    long long int ans = 0;
    int n = nums.size();

    for (int i = 7; i < 1<<n; i++) {
      bitset<5> bs(i);
      if (bs.count()==3) {
        long long int cnt = 1;
        for (int j = 0; j < n; j++) {
          if (bs[j]==1) cnt *= nums[j];
        }
        ans += cnt;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 6132
n,mat = raw_input(),[ map(int,raw_input().split()) for i in range(2)]
mem = {}
def f(mat,i,j):
	if i<0 or j <0: return -float('inf')
	if i == 0 and j == 0: return mat[i][j] 
	if (i,j) not in mem:
		mem[(i,j)] =  mat[i][j] + max(f(mat,i-1,j),f(mat,i,j-1))
	return mem[(i,j)]
print f(mat,1,len(mat[0])-1)

Measured memory_bytes: 64540
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 2019;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vl a(n + 1, 0);
  rep(i, n) a[i + 1] = (a[i] * 10 + (s[i] - '0')) % 2019;
  map<ll, ll> mp;
  ll ans = 0;
  vector<mint> p(n + 1, 1);
  rep(i, n) p[i + 1] = p[i] * 10;
  vl cnt(2019, 0);
  rep(i, n + 1) {
    mint now = p[n - i];
    now *= a[i];
    ll x = now.x;
    ans += cnt[x];
    cnt[x]++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 6808
#include <bits/stdc++.h>
//#define local
#ifdef local
    #include "dbg-macro/dbg.h"
#endif
//#define hacks
#ifdef hacks
    #include <boost/multiprecision/cpp_int.hpp>
#endif
#define p std::pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pi std::pair<int, int>
#define mp std::make_pair
#define stdabs std::abs
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (unsigned long long i = 0; i < (unsigned long long)(n); ++i)
#define vec std::vector
#define oreq |=
#define npm next_permutation
#define Yes std::cout << "Yes" << std::endl
#define No std::cout << "No" << std::endl
using namespace std;
std::vector<unsigned ll> genprimevec(const unsigned ll N);
ll extgcd(ll a, ll b, ll& x, ll& y);
ll nCr(ll n, ll r);
void stat();
template <typename T> T fact(T num);
constexpr ll mod = 1000000000 + 7;
int main()
{
    stat();
    ll n;cin>>n;
    vec<ll> h(n);
    rep(i, n) { cin >> h[i]; }
    vec<ll> sub;
    rep(i, n - 1)
    {
        if (h[i] > h[i + 1]) {
            if (h[i] - h[i + 1] > 1) {
                No;
                return 0;
            }
            sub.push_back(h[i + 1]);
        }
    }
#ifdef local
    dbg(sub);
#endif
    if(sub.size()==0){Yes;return 0;}
    rep(i, sub.size() - 1)
    {
        if (sub[i] > sub[i + 1]) {
            No;
            return 0;
        }
    }

    Yes;
    return 0;
}
ll extgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


std::vector<unsigned ll> genprimevec(const unsigned ll N)
{
    std::vector<bool> is_prime(N + 1);
    for (unsigned ll i = 0; i <= N; i++) {
        is_prime[i] = true;
    }
    std::vector<unsigned ll> P;
    for (unsigned ll i = 2; i <= N; i++) {
        if (is_prime[i]) {
            for (unsigned ll j = 2 * i; j <= N; j += i) {
                is_prime[j] = false;
            }
            P.emplace_back(i);
        }
    }
    return P;
}

void stat(){
#ifdef local
    rep(i, 2){std::cout << "local enable" << std::endl;
}
#endif
#ifdef hacks
rep(i, 2) { std::cout << "boost enable" << std::endl; }
#endif
}

ll nCr(ll n, ll r)
{
    ll num = 1;
    for (ll i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

template <typename T> T fact(T num)
{
    if (num == 1) { return 1; }
    return num * fact(num - 1);
}


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

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

    int count = 0;
    int ans = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'R'){
            count++;
        }
    }

    if(s.size()-count < count){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
aryMondai = gets.split.map(&:to_i);

W = aryMondai[0];
H = aryMondai[1];
x = aryMondai[2];
y = aryMondai[3];
r = aryMondai[4];

if (x - r) < 0 || (x + r) > W then
	puts "No";
elsif ( y - r ) < 0 || ( y + r ) > H then
	puts "No";
else
	puts "Yes";
end

Measured memory_bytes: 8684
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);


int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int dp[1010][1010];
int bingo[3][3];
bool flag[3][3];

ll n;
ll ans = 0;

void dfs(ll x, int a, int b, int c) {
	if (x > n)return;
	if (a && b && c)ans++;
	dfs(10 * x + 3, 1, b, c);
	dfs(10 * x + 5, a, 1, c);
	dfs(10 * x + 7, a, b, 1);
}

int main() {
	string s;
	cin >> s;
	int resa = 0, resb = 0;
	rep(i, 3) {
		if (s[i] == 'A')resa++;
		else resb++;
	}
	if (resa == 0 || resb == 0)puts("No");
	else puts("Yes");
	return 0;
}


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

int f(string x, string y, string z, vector<bool> xy, vector<bool> xz, vector<bool> yz)
{
    const size_t MAX = 4005;
    int ret = INT_MAX;
    for (size_t i = 0; i < MAX; i++)
    {
        for (size_t j = 0; j < MAX; j++)
        {
            if (xy[i] && xz[i + j] && yz[j])
            {
                ret = min(
                    ret,
                    (int)max({x.size(), i + y.size(), i + j + z.size()}));
            }
        }
    }
    return ret;
}

int main()
{
    vector<string> S(3);
    cin >> S[0] >> S[1] >> S[2];

    const size_t MAX = 4005;
    vector<vector<vector<bool>>> valid(3, vector<vector<bool>>(3, vector<bool>(MAX, true)));
    for (size_t i = 0; i < 3; i++)
    {
        for (size_t j = 0; j < 3; j++)
        {
            for (size_t k = 0; k < MAX; k++)
            {
                string x = S[i];
                string y = string(k, '?') + S[j];
                if (y.size() < x.size())
                {
                    swap(x, y);
                }
                for (size_t l = 0; l < x.size(); l++)
                {
                    valid[i][j][k] = valid[i][j][k] && (x[l] == '?' || y[l] == '?' || x[l] == y[l]);
                }
            }
        }
    }
    int ans = min({
        f(S[0], S[1], S[2], valid[0][1], valid[0][2], valid[1][2]),
        f(S[0], S[2], S[1], valid[0][2], valid[0][1], valid[2][1]),
        f(S[1], S[2], S[0], valid[1][2], valid[1][0], valid[2][0]),
        f(S[1], S[0], S[2], valid[1][0], valid[1][2], valid[0][2]),
        f(S[2], S[0], S[1], valid[2][0], valid[2][1], valid[0][1]),
        f(S[2], S[1], S[0], valid[2][1], valid[2][0], valid[1][0]),
    });
    cout << ans << endl;
}


Measured memory_bytes: 256
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);  
int dist(pii a,pii b){
	return abs(a.ff-b.ff)+abs(a.ss-b.ss);

} 
pii posi[100000];
int arr[312][312];
ll dp[123456];
int main(){
    std::ios::sync_with_stdio(false);
    int h,w,d;
    cin>>h>>w>>d;
    int i,j;
    rep(i,h){
    	rep(j,w){
    		cin>>arr[i][j];
    		posi[arr[i][j]]=mp(i,j);
    	}
    }
    fd(i,h*w,1){
    	if(i+d>h*w)
    		continue;
    	dp[i]=dp[i+d]+dist(posi[i],posi[i+d]);
    }
    int q;
    cin>>q;
    int l,r;
    rep(i,q){
    	cin>>l>>r;
    	cout<<dp[l]-dp[r]<<endl;
    }


    return 0;  
    
}



Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;

    int sum;
    if(n%1000 == 0) {
        sum = n/1000;
    }
    else    {
        sum = (n/1000) + 1;
    }
    int res = (sum*1000) - n;
    cout<<res<<endl;

    return 0;
}


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

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

#if DEBUG_ON
    freopen("input", "r", stdin);
#endif

    long long n, a, b;
    std::cin >> n >> a >> b;
    long long ans;
    if (a + b >= n) {
        ans = std::min(a, n);
    } else {
        long long times = n / (a + b);
        ans = times * a;
        n %= (a + b);
        ans += std::min(a, n);
    }
    std::cout << ans << '\n';
    return 0;
}

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

dic = {}
for i in range(N):
    L = list(map(int, input().split()))
    L.pop(0)
    for i in L:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1

ans = 0
for i, j in dic.items():
    if j == N:
       ans += 1

print(ans)

Measured memory_bytes: 3060
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Map<Integer, Integer> l = new HashMap<>();
        int ans = 0;
        for(int i = 0;i < N;i++){
            int a = sc.nextInt();
            if(l.containsKey(a))    l.put(a, l.get(a)+1);
            else    l.put(a, 1);
        }
        for(Integer key : l.keySet())   if(l.get(key)%2 == 1)   ans++;
        System.out.println(ans);
    }
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

const int INF = 1001001001;

struct Comb {
    vector<long long> f;
    vector<long long> rf;
    long long m;

    void init(int n, long long mod) {
        f.resize(n);
        rf.resize(n);
        m = mod;
        f[0] = 1;
        for (int i = 1; i < n; i++) {
            f[i] = (f[i - 1] * i) % mod;
        }

        for (int i = 0; i < n; i++) {
            rf[i] = inv(f[i]);
        }
    }

    long long c(int n, int k) {
        ll a = f[n];
        ll b = rf[n - k];
        ll c = rf[k];

        ll bc = (b * c) % m;
        return (a * bc) % m;
    }

    long long inv(long long x) {
        long long res = 1;
        long long k = m - 2;
        long long y = x;
        while (k) {
            if (k & 1) res = (res * y) % m;
            y = (y * y) % m;
            k /= 2;
        }
        return res;
    }
};


int main() {
    int X, Y;
    cin >> X >> Y;
    int a = 0;
    int b = 0;
    while (X > 0 && Y > 0) {
        if (X > Y) {
            X -= 2;
            Y -= 1;
            a++;
        } else {
            X -= 1;
            Y -= 2;
            b++;
        }
    }

    if (X != 0 || Y != 0) {
        cout << 0 << endl;
        return 0;
    }

    Comb c;
    c.init(a + b + 1, MOD);
    cout << c.c(a + b, a) << endl;
}

Measured memory_bytes: 10624
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

/* topologicalSort */
#define topo_SIZE 10000

vector<int> topologicalSort(vector<vector<int> > G,int n=-1){
    int indeg[topo_SIZE] = {0},u;
    vector<int> ret,ret2;
    queue<int> que;
    
    if(n==-1) n=(int)G.size();
    
    for(int i=0;i<n;i++){
        for(int j=0;j<G[i].size();j++){
            indeg[G[i][j]]++;
        }
    }
    
    for(int i=0;i<n;i++){
        if(indeg[i]==0){
            que.push(i);
        }
    }
    
    while(!que.empty()){
        u = que.front();
        que.pop();
        
        ret.push_back(u);
        
        for(int i=0;i<G[u].size();i++){
            indeg[G[u][i]]--;
            if(indeg[G[u][i]]==0){
                que.push(G[u][i]);
            }
        }
    }
    
    if(n==(int)ret.size()){
        return ret;
    }else{
        return ret2;
    }
}

int main(){
    int v,e,a,b;
    vector<int> ans;
    vector<vector<int> > in(10000);
    
    scanf("%d%d",&v,&e);
    
    for(int i=0;i<e;i++){
        scanf("%d%d",&a,&b);
        
        in[a].push_back(b);
    }
    
    ans = topologicalSort(in,v);
    
    if(ans.size()==0){
        puts("-1");
        return 0;
    }
    
    for(int i=0;i<ans.size();i++){
        printf("%d\n",ans[i]);
    }
    
    return 0;
}

Measured memory_bytes: 2508
/*  -*- coding: utf-8 -*-
 *
 * b.cc: D: Widespread
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef long long ll;

/* global variables */

ll hs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, a, b;
  scanf("%d%d%d", &n, &a, &b);

  for (int i = 0; i < n; i++) scanf("%lld", &hs[i]);
  sort(hs, hs + n, greater<int>());

  ll k0 = (hs[0] - 1) / a, k1 = (hs[0] + b - 1) / b;
  int da = a - b;
  //printf("k0=%d, k1=%d\n", k0, k1);

  while (k0 + 1 < k1) {
    ll k = (k0 + k1) / 2;

    ll an = 0, bk = b * k;
    for (int i = 0; i < n && hs[i] > bk; i++)
      an += (hs[i] - bk + da - 1) / da;

    if (an <= k) k1 = k;
    else k0 = k;
  }

  printf("%lld\n", k1);
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
  int h, w, i, k;

  while(1){
    scanf("%d %d", &h, &w);
    if(h==0 && w==0){ break; }
    for(i=0; i<h; i++){
      for(k=0; k<w; k++){
        printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2084
N, K = map(int, input().split())
a = [int(x) for x in input().split()]

dp = [''] * (K + 1)
dp[0] = 'Second'

for i in range(K+1):
    if dp[i] == '':
        dp[i] = 'Second'
        for j in a:
            if j > i:
                break
            if dp[i-j] == 'Second':
                dp[i] = 'First'
                break
    if dp[i] == 'Second':
        for j in a:
            if i + j > K:
                break
            dp[i+j] = 'First'

print(dp[K])

Measured memory_bytes: 3828
n = int(input())
h = list(map(int, input().split()))

dp = [0, abs(h[0] - h[1])]

for i in range(2, n):
    dp.append(min(dp[i - 2] + abs(h[i - 2] - h[i]), dp[i - 1] + abs(h[i - 1] - h[i])))
#print(dp)
print(dp[-1])


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

int n, q;
std::vector<int> vec, vec2;
int c = 0;

int main() {
    std::cin >> n;
    vec.assign(n, 0);
    
    for (int i = 0; i < n; i++) {
        std::cin >> vec[i];
    }
    std::cin >> q;
    vec2.assign(q, 0);
    for (int i = 0; i < q; i++) {
        std::cin >> vec2[i];
    }
    
    for (int i = 0; i < vec2.size(); i++) {
        int num = vec2[i];
        int s = 0;
        int e = vec.size();
        int mid = e / 2;
        while (s < e) {
            if (vec[mid] == num) {
                c++;
                break;
            }
            else if (num < vec[mid]) {
                e = mid;
                mid = s + (e-s) / 2;
            }
            else if (num > vec[mid]) {
                s = mid+1;
                mid =  s + ((e - s) / 2);
            }
        }
    }
    std::cout << c << std::endl;
}



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

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    int c = Integer.parseInt(sc.next());
    pw.println(Math.max(c - (a - b), 0));
  }
}


Measured memory_bytes: 22740
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M=mis()
    A=lmis()
    print(max(N-sum(A), -1))



main()



Measured memory_bytes: 10620
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<numeric>
#include<tuple>
class unionfind {
    std::vector<int> par, rank, size_;//速度ではなくメモリ効率を考えるならrankのかわりにsizeを使う
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        std::iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])std::swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};


using ll = long long;
using tp = std::tuple<int,int>;
int main(){
    int N,K;
    std::cin >> N >> K;
    if((N - 1) * (N - 2) /2 < K ) return puts("-1") * 0;
    std::vector<std::vector<int>>connect(N);
    for(int i = 1; i < connect.size(); ++i){
        connect[0].push_back(i);
        connect[i].push_back(0);
    }
    int crt = (N - 1) * (N - 2) / 2;
    for(int i = 0; i < crt - K; ++i){
        bool Exist = false;
        for(int v = 0; v < N and not Exist; ++v){
            for(int u = 0; u < N and not Exist; ++u){
                if(u == v ) continue;
                auto& nu = connect[u];
                if(std::find(nu.begin(),nu.end(),v) == nu.end()){
                    nu.push_back(v);
                    connect[v].push_back(u);
                    Exist = true;
                }
            }
        }
        if(not Exist)
            return puts("-1") * 0;
    }
    int sum = 0;
    for(auto v : connect)
        sum += v.size();
    std::cout << sum / 2 << std::endl;
    int cv = 0;
    for(auto v : connect ){
        for(auto e : v){
            if(cv < e) std::cout <<  cv + 1 << " " << e + 1 << std::endl;
        }
        ++cv;
    }
}




Measured memory_bytes: 384
n = int(input())
s = list(input())
now = 0
unclosen = 0
opened = 0
for i in s:
    if i == ")":
        now -= 1
        if opened:
            opened -= 1
        else:
            unclosen += 1
    else:
        now += 1
        opened += 1
print("(" * unclosen + "".join(s) + ")" * opened)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう

#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  int s,w;
  cin>>s>>w;
  if(s<=w)cout<<"un";
  cout<<"safe";
}

Measured memory_bytes: 3640
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 2e3 + 10;
int dp[N][N], v[N][N], w[N][N];

int main() {
  int n, X, Y;
  scanf("%d%d%d", &n, &X, &Y);
  vector<int> a;
  a.push_back(X);
  a.push_back(Y);
  while (n--) {
    scanf("%d", &X);
    a.push_back(X);
  }
  n = a.size();
  for (int i = 0; i < n; ++i) {
    dp[i][n - 1] = dp[n - 1][i] = abs(a[i] - a[n - 1]);
    v[n - 1][i] = dp[n - 1][i];
    w[i][n - 1] = dp[i][n - 1];
  }
  for (int i = n - 2; i >= 0; --i) {
    for (int j = n - 2; j >= 0; --j) {
      if (i == j) {
        v[i][j] = v[i + 1][j];
        w[i][j] = w[i][j + 1];
        continue;
      }
      if (i < j) {
        dp[i][j] = v[j + 1][j];
      } else {
        dp[i][j] = w[i][j + 1];
      }
      v[i][j] = max(v[i + 1][j], dp[i][j]);
      w[i][j] = min(w[i][j + 1], dp[i][j]);
    }
  }
  printf("%d\n", dp[0][1]);
  return 0;
}


Measured memory_bytes: 47488
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A.begin(), A.end());

	vector<pair<int,int>> CB(M);
	for (int i = 0; i < M; i++) cin >> CB[i].second >> CB[i].first;
	sort(CB.begin(), CB.end(), greater<>());

	int a = 0, c = 0;
	while (a < N && c < M) {

		if (A[a] < CB[c].first) {
			A[a] = CB[c].first;
			CB[c].second--;
			a++;
		}
		else break;

		if (CB[c].second == 0) c++;

	}

	DMP(A);
	cout << accumulate(A.begin(), A.end(), 0LL) << "\n";

	return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
//l={1,2,3,4}
//greater<int>()
//sort(l,l+N)

int main(void)
{
	string a, b, c;
	cin >> a >> b >> c;
	cout << a[0] << b[1] << c[2] << endl;

}

Measured memory_bytes: 256
H, N = map(int, input().split())
dp = [0] * (H+1)
A, B = map(int, input().split())
for j in range(1, H+1):
    dp[j] = max(dp[max(j-A,0)] + B, dp[j])
for i in range(1,N):
    A, B = map(int, input().split())
    for j in range(1, H+1):
        dp[j] = min(dp[max(j-A,0)] + B, dp[j])
print(dp[H])

Measured memory_bytes: 45404
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    s=ST()
    if s == "SUN":
        print(7)
    if s == "MON":
        print(6)
    if s == "TUE":
        print(5)
    if s == "WED":
        print(4)
    if s == "THU":
        print(3)
    if s == "FRI":
        print(2)
    if s == "SAT":
        print(1)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3572