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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  string s, t;
  cin >> s >> t;

  bool ok = true;
  map<char,char> m;
  REP(i,SZ(s)){
    char c1 = s[i];
    char c2 = t[i];

    if(!m.count(c1)){
      m[c1] = c2;
    }
    else{
      if(m[c1] != c2) ok = false;
    }
  }
  m.clear();
  REP(i,SZ(s)){
    char c1 = t[i];
    char c2 = s[i];

    if(!m.count(c1)){
      m[c1] = c2;
    }
    else{
      if(m[c1] != c2) ok = false;
    }
  }
  cout << (ok ? "Yes" : "No") << endl;

  return 0;
}


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

int main() {
	int k,a,b,c;
	c=0;
	cin >> k >> a >> b;
	for(int i=a;i<b+1;i++){
		if(i%k==0){
			c++;
		}
	}
	if(c>0){
		cout << "OK" << endl;
	}
	else{
		cout << "NG" << endl;
	}
}



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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);





void solve4ts()
{
  
  
  int n;
  cin>>n;
  string s;
  cin>>s;
  vec w(n),r(n);
  rep(i,n){
    if(s[i]=='W')
      if(i==0){
        w[i]++;
      }
      else{
        w[i]=w[i-1]+1;
      }
    else if(i!=0){
      w[i]=w[i-1];
    }
  }
  for(int i=n-1;i>=0;i--){
    if(s[i]=='R'){
      if(i==n-1){
        r[i]++;
      }
      else{
        r[i]=r[i+1]+1;
      }
    }
    else if(i!=n-1){
      r[i]=r[i+1];
    }
  }
  int ans=n;
  rep(i,n){
    if(i==0){
      chmin(ans,r[i+1]);
    }
    else if(i==n-1){
      chmin(ans,w[i-1]);
    }
    else{
      chmin(ans,max(r[i+1],w[i-1]));
    }
  }
  cout<<ans<<endl;
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

/*

g++ -std=c++1z code.cpp
./a.out

*/

Measured memory_bytes: 11460
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=10000009;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int n;
	int L[205];
	cin>>n;
	for(int i=0;i<2*n;i++){
		cin>>L[i];
	}
	sort(L,L+2*n);
	int ans=0;
	for(int i=0;i<2*n;i+=2){
		ans+=L[i];
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
using System;

namespace ConsoleApp23
{
    class Program
    {
        static void Main(string[] args)
        {


            long x = long.Parse(Console.ReadLine()) ;

            long N = (long)System.Math.Sqrt(x);

            long Ans = 0;

            //Console.WriteLine(N);

            for (int n = 1; n <= N; ++n)
            {

                if (x % n == 0 && x / n - 1 >= N+1)
                {
                    
                    Ans += x/n - 1;

                    //Console.WriteLine(n-1);
                }
            }

            Console.WriteLine(Ans);
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define inf 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
int a,b,c;
int main()
{
    while(scanf("%d%d%d",&a,&b,&c)!=EOF)
    {
        puts(a+b>=c?"Yes":"No");
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
typedef long long ll;
typedef long double ld;
#define REP(i,s,n)for(ll i=s;i<(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;



int main(){
    int A1,A2,A3;
    cin >>A1>>A2>>A3;
    int ans=A1+A2+A3;
    if(22<=ans){
        cout <<"bust"<<endl;
    }
    else{
        cout <<"win"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
int main(){
  int d[100000],n,i,ans;
  std::cin>>n;
  for (i=0;i<n;++i)std::cin >> d[i];
  std::sort(d,d+n);
  ans=d[n/2]-d[n/2-1];
  std::cout<<ans<<"\n";
}


Measured memory_bytes: 640
/*                  ___
               :                
               ;                
              :                 
              ;                 
             /                  
           o/                   
         ._/\___,                
             \                  
             /                   
             `      
	bug
*/
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

using namespace std;
#define PI 3.14159265359
#define eps 1e-8
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n)
typedef long long int ll;
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

double tick() { 
	static clock_t oldticks;
	clock_t newticks = clock();
	double diff = 1.0 * (newticks - oldticks) / CLOCKS_PER_SEC; 
	oldticks = newticks;
	return diff;
}

inline int toInt(string s){
	return atoi(s.c_str());
}

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

inline int lcm(int a,int b){
	return a*(b/gcd(a,b));
}

inline bool isPrime(int n){
	ll j;
	j=sqrt(n);

	if(n<2)
		return 0;
	for(int i=2;i<=j;i++){
		if(n%i==0)
			return false;
	}
	return true;
}

int n,m,q;
int A[505][505];

int main(){
	ios_base::sync_with_stdio(false); //Fast I/O
	cin.tie(NULL);
	//freopen("in.txt","r",stdin);
	//freopen("output.txt","w",stdout);	
	memset(A,0,sizeof(A));

	cin >> n >> m >> q;

	for(int i=0;i<m;i++){
		int a,b;;
		cin >> a >> b;
		A[a][b]++;
	}

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			A[i+1][j+1]+=A[i+1][j];
	}

	for(int i=0;i<q;i++){
		int a,b;
		cin >> a >> b;
		int cc=0;
		for(int j=a;j<=b;j++)
			cc+=A[j][b];
		cout << cc << endl;
	}
	

    //cerr << tick();

	return 0;
	
}


Measured memory_bytes: 1920
n = int(input())
s = ["".join(sorted(list(input()))) for _ in range(n)]
s.sort()
ans=0
pairs=1
for i in range(n-1):

    if s[i]==s[i+1]:
        pairs += 1
    else:      
        ans += pairs*(pairs-1)/2
        pairs =1
if pairs != 1:
    ans += pairs*(pairs-1)/2
    pairs =1
print(int(ans))

Measured memory_bytes: 16404
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b = 0;
  string s;
  
  cin >> n >> s;
  
  if(n%2==0){
    a = n/2;
    for(int i = 0;i<a;i++){
    	if(s.at(i)!=s.at(i+a)){
          b = 1;
        }
  	}
  }else{
    b = 1;
  }
  
  
  if(b>0){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n;
string s;
int q;

struct segment_tree {
  
  struct node {
    bitset<26> s;
    node() {}

    node(char x) {
      s.set(x-'a');
    }
  };
  
  node merge(node x, node y) {
    node res;
    res.s = x.s | y.s;
    return res;
  }
  ///////
  int n;
  vector<node> t;
  segment_tree() {}
  void init(int n) {
    this->n = n;
    t.resize(4*n+10);
  }
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = node(s[tl]);
    } else {
      int tm = (tl+tr)/2;
      build(2*v, tl, tm);
      build(2*v+1, tm+1, tr);
      t[v] = merge(t[2*v], t[2*v+1]);
    }
  }
  node get(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) {
      return node();
    } else if (l <= tl && tr <= r) {
      return t[v];
    } else {
      int tm = (tl + tr)/2;
      return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }
  }
  void update(int v, int tl, int tr, int idx) {
    if (tl == tr) {
      assert(tl == idx);
      t[v] = node(s[idx]);
    } else {
      int tm = (tl + tr)/2;
      if (idx <= tm) {
        update(2*v, tl, tm, idx);
      } else {
        update(2*v+1, tm+1, tr, idx);
      }
      t[v] = merge(t[2*v], t[2*v+1]);
    }
    
  }
};

segment_tree t;

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

  cin>>n;
  cin>>s;
  s = "*" + s;
  t.init(n+10);
  t.build(1,1,n);

  cin>>q;
  while (q--) {
    int z; cin>>z;
    if (z == 1) {
      int idx; char c; cin>>idx>>c;
      s[idx] = c;
      t.update(1,1,n,idx);
    } else {
      int l,r; cin>>l>>r;
      cout<<t.get(1,1,n,l,r).s.count()<<"\n";
    }
  }

  return 0;
}
// don't forget to read in the input :^)


Measured memory_bytes: 16560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(a+b>=c) {
			System.out.println(b+c);
		}else {
			int ans=0;
			ans=c-(a+b);
			int ans1=0;
			ans1=c-ans+b+1;
			System.out.println(ans1);
		}
		
	}

}


Measured memory_bytes: 23380
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){fastio
    ll n,k;cin>>n>>k;
    cout<<min(n%k,k-n%k)<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REP1(i, n) for (int i = 1; i < n + 1; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((int)(x).size())
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
typedef long long ll;
using p = pair<int, int>;
using P = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    //cout << (b - a + 1) / c << endl;
    int count = 0;
    FOR(i, a, b + 1)
    {
        if (i % c == 0)
            count++;
    }
    cout << count << endl;
}


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

int main(){
  string s;
  cin >> s;
  int start=100;
  int finish;
  for(int i=0;i<s.size();i=i+1){
    if(s.at(i) == 'A'){
      start = i;
      break;
    }
  }
  for(int i=(s.size()-1);i>=0;i=i-1){
    if(s.at(i) == 'Z'){
      finish = i;
      break;
    }
  }
  cout << finish - start + 1 << endl;
}
      
      

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(void){
    int n;
    long long a[100000],b[100000],c=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=n-1;i>=0;i--){
        a[i]+=c;
        if(a[i]%b[i]!=0){
            c+=b[i]-a[i]%b[i];
        }
    }
    cout<<c<<endl;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
  int a, b, c, d, sum=0;

   scanf("%d %d %d %d",&a,&b,&c,&d);

  if(a>=b){
    if(c>=d) sum = b + d;
    else     sum = b + c;
  }
  else {
    if(c>=d) sum = a + d;
    else     sum = a + c;
  }

  printf("%d",sum);

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    int x,t;
    cin >> x >> t;
 if(x>t) cout << x-t << endl;
 else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define MOD 1000000007LL
using namespace std;
typedef long long ll;

struct edge {
  ll U, V, W, idx;

public:
  bool operator<(const edge& e) const { return W < e.W; }
};

class UnionFind {
  vector<ll> a;

public:
  UnionFind(ll n) { REP(i, 0, n) a.push_back(-1); }
  ll find(ll i) { return a[i] < 0 ? i : (a[i] = find(a[i])); }
  bool unite(ll parent, ll child) {
    if(find(child) == find(parent)) return false;
    a[find(parent)] += a[find(child)];
    a[find(child)] = find(parent);
    return true;
  }
};

int main(void) {
  ll N, M, X;
  cin >> N >> M >> X;
  vector<edge> E(M);
  REP(i, 0, M) {
    cin >> E[i].U >> E[i].V >> E[i].W;
    E[i].U--; E[i].V--;
    E[i].idx = i;
  }

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

  ll ltX = 0, eqX = 0, gtX = 0;
  REP(i, 0, M) {
    ll cost = 0;
    UnionFind uf(N);
    for(edge e : E) if(e.idx == i) if(uf.unite(e.U, e.V)) cost += e.W;
    for(edge e : E) if(e.idx != i) if(uf.unite(e.U, e.V)) cost += e.W;
    if(cost <  X) ltX++;
    if(cost == X) eqX++;
    if(cost >  X) gtX++;
  }

  cerr << ltX << " " << eqX << " " << gtX << endl;

  vector<ll> pow2(M + 1);
  pow2[0] = 1;
  REP(i, 0, M) pow2[i + 1] = (pow2[i] * 2) % MOD;

  ll ans;
  if(eqX == 0) ans = 0;
  else if(ltX == 0) ans = (pow2[eqX] - 2 + MOD) % MOD * pow2[gtX] % MOD;
  else ans = (pow2[eqX] - 1 + MOD) % MOD * pow2[gtX] % MOD * 2 % MOD;
  cout << ans << endl;
}


Measured memory_bytes: 384
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    let n = get();
    let k = get();
    let a: Vec<usize> = (0 .. n).map(|_| get::<usize>()).filter(|&x| x < k)
        .collect();
    let n = a.len();
    // DP (O(nk))
    let mut dp = vec![vec![false; k + 1]; n + 1];
    let mut dp_rev = vec![vec![false; k + 1]; n + 1];
    let mut dp_acc = vec![vec![0; k + 1]; n + 1];
    let mut is_necessary = vec![false; n];
    dp[0][0] = true;
    for i in 0 .. n {
        for j in 0 .. k + 1 {
            if dp[i][j] {
                dp[i + 1][j] = true;
                dp[i + 1][min(j + a[i], k)] = true;
            }
        }
    }
    dp_rev[n][0] = true;
    for i in (0 .. n).rev() {
        for j in 0 .. k + 1 {
            if dp_rev[i + 1][j] {
                dp_rev[i][j] = true;
                dp_rev[i][min(j + a[i], k)] = true;
            }
        }
    }
    for i in 0 .. n + 1 {
        // cumulative sum
        let mut sum = 0;
        for j in (0 .. k + 1).rev() {
            sum += if dp_rev[i][j] { 1 } else { 0 };
            dp_acc[i][j] = sum;
        }
    }
    for i in 0 .. n {
        for j in 0 .. k {
            let opp_start = if k > j + a[i] { k - j - a[i] } else { 0 };
            let opp_end = if k - 1 > j { k - j - 1 } else { 0 };
            if dp[i][j] {
                let cnt = dp_acc[i + 1][opp_start] - dp_acc[i + 1][opp_end + 1];
                if cnt >= 1 {
                    is_necessary[i] = true;
                }
            }
        }
    }
    println!("{}", is_necessary.iter().filter(|&x| !x).count());
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 182652
#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
using LL = long long;
const int INF = 1e9;

int main(void)
{
    LL N;
    cin >> N;
    vector<int> a;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            a.push_back(i*j);
        }
    }
    sort(all(a));
    if (binary_search(all(a), N)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}



Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

print(INT() ** 3)

Measured memory_bytes: 60396
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

class LazySegmentTree{
private:
    vector<ll> node, lazy;
    ll SIZE;
    vector<bool> lazyflag;
public:
    LazySegmentTree(int n){
        SIZE = 1;
        while(SIZE<n) SIZE*=2;
        node = lazy = vector<ll>(2*SIZE+1,0);
        lazyflag = vector<bool> (2*SIZE+1,false);
    }
    void eval(int k, int l, int r){
        if(lazyflag[k]){
            node[k] += lazy[k];
            if(r-l>1){
                lazy[k*2+1] += lazy[k];
                lazy[k*2+2] += lazy[k];
                lazyflag[k*2+1] = lazyflag[k*2+2] = true;
            }
            lazyflag[k] = false;
            lazy[k] = 0;
        }
    }     
    void add(int a, int b, ll x, int k=0, int l=0, int r=-1){
        if(r<0) r=SIZE;
        eval(k,l,r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += x;
            lazyflag[k]=true;
            eval(k, l, r);
        }
        else{
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = max(node[2*k+1], node[2*k+2]);
        }
    }    
    ll getmax(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=SIZE;
        eval(k,l,r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getmax(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getmax(a, b, 2*k+2, (l+r)/2, r);
        return max(vl, vr);
    }
};

int N,M;
int main(){
    cin >> N >> M;
    vector<vector<pair<int,ll>>> v(N+1);
    int l,r;
    ll a;
    for(int i=0;i<M;i++){
        cin >> l >> r >> a;
        v[r].push_back({l,a});
    }
    LazySegmentTree segtree(N+1);
    for(int i=1;i<=N;i++){
        ll sum = 0;
        for(auto x:v[i]) sum += x.second;
        segtree.add(i,i+1,sum+segtree.getmax(1,i));
        for(auto x:v[i]) segtree.add(x.first,i,x.second);
    }
    cout << segtree.getmax(1,N+1) << endl;
}

Measured memory_bytes: 20480
/**
 *    author:  FromDihPout
 *    created: 2020-06-25
**/

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


bool check(string s, vector<bool> &a, int n) {
    for (int i = 1; i < n - 1; i++) {
        if ((a[i] && s[i] == 'o') || (!a[i] && s[i] == 'x')) {
            a[i + 1] = a[i - 1];
        }
        else {
            a[i + 1] = !a[i - 1];
        }
    }
    
    bool valid;
    if ((a[0] && s[0] == 'o') || (!a[0] && s[0] == 'x')) {
        valid = a[n - 1] == a[1];
    }
    else {
        valid = a[n - 1] != a[1];
    }
    
    if (!valid) return false;
    
    if ((a[n-1] && s[n-1] == 'o') || (!a[n-1] && s[n-1] == 'x')) {
        valid = a[n - 2] == a[0];
    }
    else {
        valid = a[n - 2] != a[0];
    }
    return valid;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    vector<pair<bool, bool>> possibilities =
    {{1, 1}, {1, 0}, {0, 1}, {0, 0}};
    vector<bool> a(n);
    for (auto p : possibilities) {
        a[0] = p.first;
        a[1] = p.second;
        if (check(s, a, n)) {
            for (int i = 0; i < n; i++) {
                if (a[i])
                    cout << 'S';
                else
                    cout << 'W';
            }
            cout << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    
    return 0;
}

Measured memory_bytes: 3744
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<int> t(n+1);
    vector<int> x(n+1);
    vector<int> y(n+1);
    for (int i = 1; i <= n; i++) {
        cin >>t[i]>>x[i]>>y[i];
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        int d = abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
        int dt = t[i] - t[i-1];
        if (dt < d) {
            flag = false;
        } else {
            if ((dt % 2 == 0) && (d % 2 == 1) ) {
                flag = false;
            }
            if ((dt % 2 == 1) && (d % 2 == 0) ) {
                flag = false;
            }
        }
    }
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}




Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int i,x,c;
	for(i=1;i<=5;i++)
	{
		cin>>x;
		if(x==0)
			c=i;
	}
	cout<<c;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n;
int cnt0,cnt1;
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		if(read()&1)++cnt1;
		else ++cnt0;
	}
	while(cnt1>1)++cnt0,cnt1-=2;
	puts(cnt1&&cnt0?"NO":"YES");
	return 0;
}


Measured memory_bytes: 3596
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


N, M = map(int, input().split())
A = [0]*(M+1)
B = [0]*(M+1)
for i in range(1, M+1):
    A[i], B[i] = map(int, input().split())


##
v = N+1
uni = [-1]*v  # 根であれば *そのグループの要素数(負)* が、子であれば親の番号が入る。
              # 初期値に -1 を入れておく
              # v は頂点数

# 頂点 v の所属するグループを調べる
def root(v):
    if uni[v] < 0:  # v が親の場合
        return v
    else:           # v が子の場合
        uni[v] = root(uni[v])  # 親のrootを調べる
        return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b):
    # まずはそれぞれ根の番号に置き換える
    ra = root(a)
    rb = root(b)
    if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
        return False
    
    # ra を大きなグループにしたいので、逆であれば入れ替える
    if uni[ra] > uni[rb]: # rbの方が要素数が多ければ
        ra, rb = rb, ra

    # ra と rb を結合し、rb の親を ra とする
    uni[ra] += uni[rb]
    uni[rb] = ra
    return True

# 頂点 a, b が同じグループであるかを調べる
def isConnect(a, b):
    return root(a) == root(b)

# 頂点 a を含むグループの頂点数を調べる
def size(a):
    return -uni[root(a)]


base = (N * (N-1)) // 2
bene = 0
ans = [base]
for i in reversed(range(2, M+1)):
    a, b = A[i], B[i]

    if not isConnect(a, b):
        bene += size(a) * size(b)
        connect(a, b)
    ans.append(base-bene)

for e in reversed(ans):
    print(e)


Measured memory_bytes: 94212
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>

using namespace std;

int main(void) {
	int p[4];
	int a, b;
	for (int i = 0; i < 4; i++) {
		p[i] = 0;
	}
	for (int i = 0; i < 3; i++) {
		scanf("%d %d", &a, &b);
		p[a - 1]++;
		p[b - 1]++;
	}
	int c1, c2;
	c1 = 0;
	c2 = 0;
	for (int i = 0; i < 4; i++) {
		if (p[i] == 1) { c1++; }
		if (p[i] == 2) { c2++; }
	}
	if (c1 == 2 && c2 == 2) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}

}

Measured memory_bytes: 128
fun main(args: Array<String>){
    val (h, w) = readLine()!!.split(" ").map(String::toInt)
    val n = readLine()!!.toInt()
    val al = readLine()!!.split(" ").map(String::toInt)
    val ms = mutableListOf<Int>()
    al.forEachIndexed {
        index, a -> for (i in 0 until a) ms.add(index + 1)
    }
    for (j in 0 until h) {
        val output = if (j % 2 == 0) ms.slice((j * w) until ((j + 1) * w))
                     else ms.slice((j * w) until ((j + 1) * w)).reversed()
        output.forEachIndexed {
            index, o -> print(o.toString() + if (index < w - 1) " " else "\n")
        }
    }
}


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

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/


#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("d",&a,&b)
#define sfff(a,b,c)     scanf("d%d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int z=1 ; z<=t ; z++)
#define PRINT_CASE printf("Case %d: ",z)
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2



int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = 100005;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
int n,k,a[102];

int win_dp[maxn];

int cal(int stone)
{
    //if(val==0) return 1;
    if(stone<a[1]) return 0;

    int &win=win_dp[stone];
    if(win!=-1){
        return win;
    }
    win=0;
    f1(i,n) if(a[i]<=stone)
    win|=!cal(stone-a[i]);

    return win;
}

int main() {
	CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin>>n>>k;

    f1(i,n) cin>>a[i],win_dp[a[i]]=1;


    memset(win_dp , -1 , sizeof(win_dp));


    int win=cal(k);
    if(win) cout<<"First"<<endl;
    else cout<<"Second"<<endl;

    return 0;
}


Measured memory_bytes: 5376
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a[200010],ans=0,now0=0;
    cin>>n;
    rep(i,n){
        cin>>a[i];
    }
    if(a[0]!=0){
        cout<<-1<<endl;
        return 0;
    }
    rep2(i,1,n){
        if(a[i]==0){
            now0=i;
        }
        if(a[i]==a[i-1]+1){
            ans++;
        }
        else{
            if(i-now0<a[i] || a[i-1]<a[i]-1){
                ans=-1;
                break;
            }
            else{
                ans+=a[i];
            }
        }
        // cout<<i<<" "<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

int count=0;

std::vector<long int> merge(std::vector<long int> v1, std::vector<long int> v2) {
    int c1=0, c2=0;
    std::vector<long int> sorted;
    while (true) {
        if (c1 < v1.size()) {
            count++;
            if (c2 < v2.size()) {
                if (v1[c1] < v2[c2]) {
                    sorted.push_back(v1[c1]);
                    c1++;
                } else {
                    sorted.push_back(v2[c2]);
                    c2++;
                }
            } else {
                sorted.push_back(v1[c1]);
                c1++;
            }
        } else {
            if (c2 < v2.size()) {
                count++;
                sorted.push_back(v2[c2]);
                c2++;
            } else {
                break;
            }
        }
    }
    return sorted;
}

std::vector<long int> merge_sort(std::vector<long int> v) {
    if (v.size() == 1) {
        return v;
    } else {
        std::vector<long int> half1(v.size()/2);
        std::vector<long int> half2(v.size()-v.size()/2);
        std::copy(v.begin(), v.begin()+(v.size()/2), half1.begin());
        std::copy(v.begin()+(v.size()/2), v.end(), half2.begin());
        return merge(merge_sort(half1), merge_sort(half2));
    }
}

int main() {
    int n;
    std::vector<long int> S;
    std::cin >> n;
    for (int i=0; i<n; i++) {
        long int s;
        std::cin >> s;
        S.push_back(s);
    }

    auto ans=merge_sort(S);
    for (int i=0; i<n-1; i++) {
        std::cout << ans[i] << " ";
    }
    std::cout << ans[n-1] << std::endl << count << std::endl;

    return 0;
}


Measured memory_bytes: 32816
#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def isMultiple(s, m):
    tmp = 0
    for i in range(len(s)):
        tmp = (tmp * 10 + int(s[i])) % m
        if tmp == 0:
            return i
    return -1


k = int(readline())
acc = "7" * 50000000
if k % 2 == 0:
    ans = -1
else:

    ans = isMultiple(acc, k)
    if ans != -1:
        ans += 1

print(ans)


Measured memory_bytes: 165028
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  unsigned N;
  std::cin >> N;
  std::vector<unsigned> A(N);
  for (auto &i : A) {
    std::cin >> i;
  }
  std::sort(A.begin(), A.end());
  unsigned ans = 0u;
  unsigned even = 0u;
  unsigned tmp = 0u;
  unsigned keep = 0u;
  for (unsigned i = 0; i < N; ++i) {
    if (keep != A[i]) {
      if (tmp % 2 == 0) {
        ++even;
      }
      ++ans;
      keep = A[i];
      tmp = 1;
    } else {
      ++tmp;
    }
  }
  if (tmp % 2 == 0) {
    ++even;
  }
  if (even % 2 == 0) {
    --ans;
  }
  std::cout << ans;
  return 0;
}

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

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int input[] = new int[n];
		int ball[] = new int[200001];
		

		for(int i = 0; i < n; i++){
			input[i] = scan.nextInt()-1;
		}
		
		Arrays.fill(ball, 0);
		for(int i = 0; i < n; i++){
			ball[input[i]] ++;
		}
		
		long sum = 0;
		
		for(int i = 0; i < 200001; i++){
			long x = ball[i];
			sum += (x * (x - 1))/2; 
		}

		for(int i = 0; i < n; i++){
			int x = input[i];
			long y = ball[x];
			long z = Math.max(y - 1, 0);
			System.out.println(sum - ((y * (y - 1))/2) + ((z * (z - 1))/2));
		}
	}
}

Measured memory_bytes: 92804
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rnfor(i,a,b) for(ll (i) = (a) - 1; (i) >= (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    rep1(i, k)r = r * n-- / i;
    return r;
}

int main(){
    ll k,a,b;
    cin >> k >> a >> b;
    ll ans = 1;
    if(b - 2 <= a)pf(k + 1);
    else{
        k -= a - 1;
        ans += a - 1;
        ans += (b - a) * (k / 2);
        if(k % 2 == 1)++ans;
        pf(ans);
    }
    return 0;
}


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

int main()
{
	float a, b, c, d, e, f;
	while (scanf("%f %f %f %f %f %f", &a, &b, &c, &d, &e, &f) != EOF)
	{
		float x = ((c * e) - (b * f)) / ((a * e) - (b * d));
		float y = ((a * f) - (c * d)) / ((a * e) - (b * d));
		if (x <= 0.0000 &&x > -0.0005)x = 0.000;
		if (y <= 0.0000 &&y > -0.0005)y = 0.000;
		printf("%.3f %.3f\n", x, y);
	}
}

Measured memory_bytes: 1076
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	long long a,b,c;
	cin>>a>>b>>c;
	int f;
	bool h=false;
	for(int i=0;i<=1000;i++){
		if(a%2==1||b%2==1||c%2==1){
			f=i;h=true;break;
		}
		int a1,b1,c1;
		a1=a;
		b1=b;
		c1=c;
		a=b1/2+c1/2;
		b=a1/2+c1/2;
		c=a1/2+b1/2;		
	}
	if(h==true)
		cout<<f<<endl;
	else
		cout<<"-1"<<endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <random>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);

    string s;
    cin >> s;

    int N;
    cin >> N;
    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        string t;
        cin >> t;
        t += t;
        if (t.find(s) != -1)
            ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3224
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/05/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int N,W; cin >> N >> W;
  constexpr int VMAX = 1e5;
  vector<ll> dp(VMAX+1, W+1);
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    ll w,v; cin>>w>>v;
    for (int t = VMAX-v; t >= 0; t--) {
      if (dp[t] + w > W)
        continue;
      dp[t+v] = min(dp[t+v], dp[t] + w);
    }
  }
  int ans = VMAX;
  while (ans > 0 and dp[ans] > W)
    --ans;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<limits>
#include<string.h>
#include<vector>
#include<stack>
#include<queue>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a,b;
    int count=0;
    int c=0;
    for (int i = 0; i < n; i++)
    {
        cin>>a>>b;
        if (a==b)
        {
            count++;
            if (count==3)
            {
                c=1;
            }
            
        }else
        {
            count=0;
        }
        
        
    }
    if (c==1)
    {
        cout<<"Yes"<<endl;
    }else
    {
        cout<<"No"<<endl;
    }
    
    


    return 0;
}

Measured memory_bytes: 3128
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.List

main = do
  n <- readLn :: IO Int
  a <- getIntListBC
  let a' = sum . map (\x -> (length x) - 1) . group . sort $ a
  if even a' then print $ n - a'
             else print $ n - a' - 1

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine


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

int main() {
  int n,l;
  cin >> n >> l;
  string a[110];
  for(int i=0;i<n;i++) cin >> a[i];
  sort(a,a+n);
  string s;
  for(int i=0;i<n;i++){
    s += a[i];
  }
  
  cout << s << endl;
  
  return 0;
}

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

typedef long long ll;

#define PB push_back
#define MP make_pair

const int mxN = 2e5;
ll c[mxN + 1];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        c[i % k]++;
    }

    if (k & 1) cout << c[0] * c[0] * c[0] << "\n";
    else cout << c[0] * c[0] * c[0] + c[k / 2] * c[k / 2] * c[k / 2] << "\n";
}

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

int main() {
	// your code goes here
	string x;
	cin >> x;
	
	int y[3];
	y[0]= stoi (x.substr(0,1));
	y[1]= stoi (x.substr(1,1));
	y[2]= stoi (x.substr(2,1));
	int s = y[0] + y [1] + y[2];
	
	std::cout << s << std::endl;

}


Measured memory_bytes: 256
import sys

numChar = 26
ordA = ord('a')

Ss = input().rstrip()
Ts = input().rstrip()

setS, setT = set(Ss), set(Ts)
for T in setT:
    if T not in setS:
        print(-1)
        sys.exit()

def getDistNextss(As, numChar):
    lenA = len(As)
    poss = [-1] * numChar
    for i, A in enumerate(As):
        if poss[A] == -1:
            poss[A] = i + lenA
    distNextss = [[0]*(numChar) for _ in range(lenA)]
    for i in reversed(range(lenA)):
        poss[As[i]] = i
        distNextss[i] = [pos-i for pos in poss]
    return distNextss

As = [ord(S)-ordA for S in Ss]
distNextss = getDistNextss(As, numChar)

lenS = len(Ss)
i = 0
for T in Ts:
    T = ord(T) - ordA
    i += distNextss[i%lenS][T]
    i += 1

print(i)


Measured memory_bytes: 126452
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;

// Kruskal法
//   証明: http://drken1215.hatenablog.com/entry/20121223/1356230697

class UnionFind {
    vector<int> par;
    int n;
public:
    UnionFind(int sz) : par(sz, -1) {}
    int find(int x) {
        if (par[x] < 0) return x;
        return par[x] = find(par[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -par[find(x)]; }
};

int kruskal(vector<vector<P>> &edge) {
    int n = edge.size();
    typedef pair<int, P> PP;
    vector<PP> weights;
    for (int i = 0; i < n; i++) {
        for (auto &e : edge[i]) weights.push_back({e.second, {i, e.first}});
    }
    sort(weights.begin(), weights.end());
    UnionFind uf(n);
    int ret = 0;
    for (auto &w : weights) {
        int from = w.second.first;
        int to = w.second.second;
        if (uf.unite(from, to)) ret += w.first;
    }
    return ret;
};


// verified
//   http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp
void AOJ_GRL_2_A() {
    int V, E;
    cin >> V >> E;
    vector<vector<P>> edge(V);
    for (int i = 0; i < E; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        edge[s].push_back({t, w});
    }
    cout << kruskal(edge) << endl;
}

int main() {
    AOJ_GRL_2_A();
    return 0;
}


Measured memory_bytes: 6212
n,k = map(int,input().split())
H = list(map(int,input().split()))
dp = [10**10]*n
dp[0] = 0
for i in range(n):
	for j in range(1,k+1):
		if i+j < n:
			dp[i+j] = min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[n-1])

Measured memory_bytes: 52448
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef vector<int > vecint;
typedef vector<ll > vecll;
typedef vector<vector<int > > vec2int;
typedef vector<bool > vecbool;
typedef vector<string > vecstr;
////////////////////////////////////////////////
int main()
{
  int n; cin >> n;
  int a; cin >> a;
  vecint x(n,0);
  REP(i,n)cin >> x[i];
  // sort(all(x));
  int kmax = n*a;
  vector<vector<vector<ll>>> dp(n + 1, vector<vecll> (n + 1, vecll(kmax + 1, 0)));
  REP(i,n + 1){
    dp[i][0][0] = 1;
  }
  for(int i = 1;i <= n; i ++ ){
    for(int j = 1;j <= i; j ++ ){
      for(int k = 1;k <= kmax; k ++ ){
  	dp[i][j][k] = dp[i - 1][j][k];
  	if(k - x[i - 1] >= 0){
  	  dp[i][j][k] += dp[i - 1][j - 1][k - x[i - 1]];
  	}
      }
    }
  }
  ll ans = 0;
  REP(j, n + 1){
    if(j == 0)continue;
    ans += dp[n][j][j*a];
  }
  cout << ans << endl;
}


Measured memory_bytes: 52224