akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll mod = 1e9 + 7;

string x;
int d;

ll dp[110][10100][2];

int main() {
	cin>>x;
	cin>>d;

	dp[0][0][0] = 1LL;
	for(int i=0;i<x.length();i++) {
		for(int j=0;j<d;j++) {
			int ni = i + 1;

			//cout<<"With "<<i<<" digits with "<<j<<" -> "<<dp[j][i][0]<<" and "<<dp[j][i][1]<<"\n";

			for(int nd=0;nd<=9;nd++) {
				int ndiv = (j+nd)%d;
				if(nd < int(x[i]-'0')) {
					// place each possible digit, convert 0s into 1s
					dp[ndiv][ni][1] += (dp[j][i][0] + dp[j][i][1])%mod;
					dp[ndiv][ni][1] %= mod;
				}
				else if(nd == int(x[i]-'0')) {
					// special case for 0s
					dp[ndiv][ni][0] += dp[j][i][0];
					dp[ndiv][ni][0] %= mod;

					dp[ndiv][ni][1] += dp[j][i][1];
					dp[ndiv][ni][1] %= mod;
				}
				else {
					// normal case for 1s, no place for 0s
					dp[ndiv][ni][1] += dp[j][i][1];
					dp[ndiv][ni][1] %= mod;
				}
			}
		}
	}

	cout<<(dp[0][x.length()][0]+dp[0][x.length()][1]+mod-1)%mod<<"\n";
}

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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int main() {
  ios:: sync_with_stdio(false);
  cin.tie();
  string s;
  cin >> s;
  for (auto c : s) {
    if (c == 'A') {
      cout << 'T';
    } else if (c == 'T') {
      cout << 'A';
    } else if (c == 'G') {
      cout << 'C';
    } else {
      cout << 'G';
    }
  }
  return 0;
}




Measured memory_bytes: 3616
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;


int dp[1000000];

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

  int n;
  cin >> n;

  
  /*
  int res = n;
  REP(i, n+1){
    int cc=0;
    int t=i;
    while(t>0) cc += t%6, t/=6; //6^* で割れるだけ割る
    t = n-i;
    while(t>0) cc += t%9, t/=9; //9^* で割れるだけ割る
    if(res > cc) res = cc; //これまでの中で最も小さいのを採用
  } 

  cout << res << endl;

  int test = 13;
  int cc = 0;
  cc += test%6, test/=6;
  
  //cout << cc << " " << test << endl;
  */
  
  REP(i, n+1) dp[i] = i;
  dp[0] = 0;
  
  for(int i=6; i < n+1; i++){
    for(int j=6; j <= i; j *= 6){
      dp[i] = min(dp[i-j] + 1, dp[i]);
    }
  }

  for(int i=9; i < n+1; i++){
    for(int j=9; j <= i; j *= 9){
      dp[i] = min(dp[i-j] + 1, dp[i]);
    }
  }
  
  cout << dp[n] << endl;    
  
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int main(void)
{
	long int n,i,a,b,M,m;
	scanf("%ld",&n);
	b=0;
	a=0;
	M=-1000000;
	m=1000000;
	for(i=1;i<=n;i++)
		{scanf("%ld",&a);
		b=b+a;
			if(a>M){M=a;}
			if(a<m){m=a;}}
	printf("%ld %ld %ld\n",m,M,b);
return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string S;
    cin >> S;
    
    int l = S.size();
    for(int i=0;i<l;i++){
        for(int j=0;j<i;j++){
            if(S[i] == S[j]){
                cout << "no" << endl;
                return 0;
            }
        }
    }

    cout << "yes" << endl;

}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
d_l = {}
d_r = {}
ans = 0
for i, x in enumerate(a):
    l = i + x
    r = i - x
    if i == 0:
        d_l[l] = 1
    elif i == n - 1:
        if r in d_r:
            d_r[r] += 1
        else:
            d_r[r] = 1
    else:
        if l in d_l:
            d_l[l] += 1
        else:
            d_l[l] = 1
        if r in d_r:
            d_r[r] += 1
        else:
            d_r[r] = 1
for i, j in d_l.items():
    if i in d_r.keys():
        ans += j * d_r[i]
print(ans)

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

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template<typename Head> void dump(Head&& head) { cerr << head; dump(); }
template<typename Head, typename... Tail> void dump(Head&& head, Tail&&... tail) { cerr << head << ", "; dump(forward<Tail>(tail)...); }
#define debug(...) do {cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; dump(__VA_ARGS__); } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////

const ll inf = 1LL<<60;

int main()
{
  ll n,k; cin>>n>>k;
  vector<ll> v(n);
  rep(i, n) cin>>v[i];

  ll ans = 0;
  for (int l=0; l<=n; l++) for (int r=0; l+r<=n; r++) {
    ll c = k-l-r;
    if (c < 0) continue;

    vector<ll> a;
    for (int i=0; i<l; i++) a.push_back(v[i]);
    for (int i=0; i<r; i++) a.push_back(v[n-1-i]);
    sort(a.rbegin(),a.rend());
    while (!a.empty() && a.back() < 0 && c>0) {
      a.pop_back();
      c--;
    }

    ll sum = 0;
    for (auto aa:a) sum += aa;
    ans = max(ans, sum);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3604
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Main{
 
static final PrintWriter out=new PrintWriter(System.out);
 
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line="";
while((line=br.readLine())!=null&&!line.isEmpty()){
int ans=0;
int n=Integer.parseInt(line);
ArrayList<Integer> array=new ArrayList<Integer>();
StringTokenizer st1=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
int a=Integer.parseInt(st1.nextToken());
array.add(a);
}
int m=Integer.parseInt(br.readLine());
StringTokenizer st2=new StringTokenizer(br.readLine());
for(int i=0;i<m;i++){
int b=Integer.parseInt(st2.nextToken());
if(array.indexOf(b)>=0) ans++;
}
out.println(ans);
out.flush();
}
}
}

Measured memory_bytes: 23520
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

#define rep(i,n) for(int i=0; i<(int)(n); i++)

const int mod = 1000000007;

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

  long n, a, b;
  cin >> n >> a >> b;

  vector<long> h(n);
  fillLong(h, n);
  sortvinv(h);
  
  long ub = INF;
  long lb = 0;

  while (ub-lb > 1) {
    long next = (ub+lb)/2;
    long res = 0;
    rep(i, n) {
      long rem = h[i]-b*next;
      if (rem > 0) {
        res += (rem+a-b-1)/(a-b);
      }
    }
    if (res <= next) {
      ub = next;
    } else {
      lb = next;
    }
  }
  cout << ub << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pye cout << "yes" << endl;
#define pno cout << "no" << endl;
#define pYe cout << "Yes" << endl;
#define pNo cout << "No" << endl;
#define pYE cout << "YES" << endl;
#define pNO cout << "NO" << endl;
#define end return 0;
#define prin(num) cout << num << endl;
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 100000000000
#define MOD 1000000007LL
#define MAX 200005
#define NIL -1
#define WHITE 0
#define BLACK 1
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

int main(void) {
    ll N, C, K;
    cin >> N >> C >> K;
    ll t[100000], i;
    
    for(i=0; i<N; i++) {
        cin >> t[i];
    }
    sort(t, t+N);
    ll ans=0;
    ll cnt;
    for(i=0; i<N; ) {
        ll j=i;
        cnt=1;
        i++;
        while(t[i]<=t[j]+K && cnt<C) {
            i++;
            cnt++;
        }
        
        ans++;
    }
    
    prin(ans)
}


Measured memory_bytes: 1024
#define rep(i,n) REP(i,0,n)
#define REP(i, a, b) for(int i = a; i < (int)(b); i++)
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


int main(void) {
   ll P,Q,R;
   cin>>P>>Q>>R;
   cout<<min(min(P+Q,P+R),Q+R)<<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 n = sc.nextInt();
        int k = sc.nextInt();
        if (n % k == 0) {
            System.out.println(0);
            return;
        }
        System.out.println(1);
    }

}


Measured memory_bytes: 23124
def I(): return int(input())
def S(): return input()
N = I()
S = S()
s1,s2,s3 = set(),set(),set()
for x in S:
    for z in s2:
        s3.add(z+x)
    for y in s1:
        s2.add(y+x)
    s1.add(x)
print(len(s3))


Measured memory_bytes: 3188
#include<stdio.h>
#include<string.h>

int main() {
	int A;
	int B;
	int C;
	unsigned long int D;
	int E;
	unsigned long int ans = 0;
  	int CC = 0;
	int i = 1;

	scanf("%d %d", &A, &B);

	if (A >= B) {
		C = A;
		E = B;
	}
	else {
		C = B;
		E = A;
	}
	
	while (CC == 0) {
		D = C * i;
		if (D % E == 0) {
			ans = D;
          	CC = 1;
		}
		i = i + 1;
	}
	
	printf("%lu", ans);
  

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 420000
#define lowbit(x) (x&-x)
using namespace std;
int a[N],c[N],n,sum[N];
namespace T{
	int t[N];
	int get(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i))ans+=t[i];
		return ans;
	}
	int add(int x,int a){
		for(int i=x;i<=320000;i+=lowbit(i))t[i]+=a;
	}
	int clear(){
		memset(t,0,sizeof(t));
	}
}
int check(int x){
	T::clear();
	long long ans=0;
	for(int i=1;i<=n;i++)c[i]=a[i]>=x?1:-1;
//	for(int i=1;i<=n;i++)printf("%d ",c[i]);
	T::add(120000,1);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+c[i];
		ans+=T::get(sum[i]+120000);
		T::add(sum[i]+120000,1);
		
	}
	return ans>=(1LL*n*(n+1)/2+1)/2;
}
int main(){
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(a[i],mx);
	int l=1,r=mx;
//	for(int i=1;i<=mx;i++)printf("%d %d\n",i,check(i));
//	printf("%d\n",check(29));
	while(r-l>=3){
		int mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	} 
//	printf("%d %d\n",r,l);
	for(int i=r;i>=l;i--){
		if(check(i)){
			printf("%d\n",i);
			return 0;
		}
	}
}

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

int main(){
	int n; cin >> n;
	if(n<=9){
		cout << n << endl;
		return 0;
	}
	else if(10<=n&&n<=99){
		cout << 9 << endl;
		return 0;
	}
	else  if(100<=n&&n<=999){
		cout << 9+(n-99) << endl;
		return 0;
	}
	else if(1000<=n&&n<=9999){
		cout << 9+(999-99) << endl;
	}
	else if(n==100000){
		cout << 90909 << endl;
		return 0;
	}
	else{
		cout << 9+900+(n-9999) << endl;
		return 0;
	}
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m1 = sc.nextInt();
        int d1 = sc.nextInt();
        int m2 = sc.nextInt();
        int d2 = sc.nextInt();
        System.out.println(m1 != m2 ? 1 : 0);
        sc.close();

    }

}


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


ll pref[1000];
ll dp[500][500];

ll solve(ll a[],ll i,ll j)
{
	if(i>=j)
	{
		return(0);
	}
	if(dp[i][j]!=-1)
	{
		return(dp[i][j]);
	}
	ll ans=1000000000000000000;
	ll k;
	for(k=i;k<j;k++)
	{
		ans=min(ans,pref[j]-pref[i-1]+solve(a,i,k)+solve(a,k+1,j));
	}
	return(dp[i][j]=ans);
}
int main()
{
	ll n,i;
	cin>>n;
	ll a[n+1];
	pref[0]=0;
	ll sum=0;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		pref[i]=sum;
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(a,1,n)<<"\n";
}

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

int main() {
    int N;
    cin >> N;
    int d = N % 10;
    string ans = "hon";
    if (d == 3) ans = "bon";
    if (d == 0 || d == 1 || d == 6 || d == 8) ans = "pon";
    cout << ans << endl;
}

Measured memory_bytes: 3624
import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

M = []
for i in range(1,N+1):
    M.append(i)

L = list(itertools.permutations(M))

cnt = 0
pc = 0
qc = 0
for i in range(len(L)):
    cnt+=1
    K = list(L[i])
    if K==P:
        pc = cnt
    if K==Q:
        qc = cnt

print(abs(pc-qc))

Measured memory_bytes: 8052
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = []
for i in range(M):
  B, C = map(int, input().split())
  D.append([C, B])
D.sort(reverse=True)
E = []
j = 0
for i in range(N):
  if j < M:
    if D[j][1] == 0:
      j += 1
    if j == M:
      E.append(0)
    else:
      E.append(D[j][0])
      D[j][1] -= 1
  else:
    E.append(0)
S = 0
for i in range(N):
  S += max(A[i], E[i])
print(S)

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

int main()
{
  int n,wmax;cin>>n>>wmax;
  vector<int> w(n);
  vector<int> v(n);
  int i,j;
  int vmax=0;
  int inf=wmax+1;
  for(i=0;i<n;i++)cin>>w.at(i)>>v.at(i);
  for(i=0;i<n;i++)vmax+=v.at(i);
  vector<vector<int>> dp(n+1,vector<int>(vmax+1,inf));
  for(i=0;i<=n;i++)dp[i][0]=0;
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=vmax;j++)
    {
      if(j-v[i-1]>=0)dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);
      else dp[i][j]=dp[i-1][j];
    }
  }
  int ans=0;
  for(i=0;i<=vmax;i++)if(dp[n][i]<inf)ans=i;
  cout<<ans<<endl;
}


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

int main()
{  string s,t;
    cin>>s>>t;
    int c=0;
    for(int i=0;i<s.length();i++)
    {

        if(s[i]!=t[i])
           {
            s[i]=t[i];
            c++;
            }
        else
            s[i]=t[i];

    }
    cout<<c<<endl;
return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int N; cin >> N;
    int c500 = 0, c5 = 0;
    while(N >= 500){
        c500++;
        N -= 500;
    }
    while(N >= 5){
        c5++;
        N -= 5;
    }
    int ans = c5*5 + c500*1000;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include   <cstring>
#include    <cstdio>
#include     <queue>
using namespace std;

const int MAXN = 200+9;
struct E{
	int next,to,val;
}edge[(MAXN*MAXN)<<1];
int head[MAXN],edge_num=1;
int mat[MAXN][MAXN];
int idx;

void addedge(int x,int y,int v){
	edge[++edge_num].next=head[x];
	edge[edge_num].to=y;
	edge[edge_num].val=v;
	head[x]=edge_num;
}

namespace Network_Flows{
	const int INF = 1000000000+7;
	int depth[MAXN*MAXN+MAXN];
	int iter[MAXN*MAXN+MAXN];
	int S,T;

	void clear(){
		edge_num=1;
		memset(head,0,sizeof(head));
	}

	void link(int x,int y,int v){
		addedge(x,y,v);addedge(y,x,0);
	}

	bool BFS(){
		static queue<int> que;
		memset(depth,-1,sizeof(depth));
		que.push(S);depth[S]=0;
		while(!que.empty()){
			int fro=que.front();que.pop();
			for(int i=head[fro];i;i=edge[i].next){
				int v=edge[i].to;
				if(edge[i].val>0 && depth[v]==-1){
					depth[v]=depth[fro]+1;
					que.push(v);
				}
			}
		}
		return depth[T]!=-1;
	}

	int DFS(int x,int f){
		if(x==T)return f;
		for(int &i=iter[x];i;i=edge[i].next){
			int v=edge[i].to;
			if(edge[i].val>0 && depth[v]==depth[x]+1){
				int tmp=DFS(v,min(f,edge[i].val));
				if(tmp>0){
					edge[i].val-=tmp;
					edge[i^1].val+=tmp;
					return tmp;
				}
			}
		}
		return 0;
	}

	int Dinic(){
		int re=0;
		while(BFS()){
			memcpy(iter,head,sizeof(head));
			while(true){
				int tmp=DFS(S,INF);
				if(tmp==0)break;
				re+=tmp;
			}
		}
		return re;
	}
}

int main(){
	int n;scanf("%d",&n);
	using Network_Flows::S;
	using Network_Flows::T;
	S=(n<<1)+1;
	T=(n<<1)+2;
	using Network_Flows::link;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		mat[x][y]=i;
		link(i,T,1);
	}
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		for(int j=0;j<=x;j++){
			for(int k=0;k<=y;k++){
				if(mat[j][k])
					link(i+n,mat[j][k],Network_Flows::INF);
			}
		}
		link(S,i+n,1);
	}
	int ans=Network_Flows::Dinic();
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <cassert>
#include <iterator>
using namespace std;
using VI = vector<long>;

long p[100][11];

int popcnt(int k) {
    int cnt = 0;
    while (k) {
        cnt += k & 1;
        k >>= 1;
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    VI eigyo(n);
    for (int i = 0; i < n; i++) {
        int res = 0, f;
        for (int j = 0; j < 10; j++) {
            cin >> f;
            res |= f;
            if (j != 9) {
                res <<= 1;
            }
        }
        eigyo[i] = res;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 10; j++) {
            cin >> p[i][j];
        }
    }
    
    long profit = -1e18;
    for (int i = 1; i < 1024; i++) {
        long tmp = 0;
        for (int j = 0; j < n; j++) {
            int kaburi = eigyo[j] & i;
            int pop = popcnt(kaburi);
            assert(0 <= pop && pop <= 10);
            tmp += p[j][pop];
        }
        profit = max(profit, tmp);
    }
    cout << profit << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 1000001
#define pb push_back
using namespace std;

int n,g;
bool var[maxn];
vector<int> primes[maxn];

int gcd(int x , int y) {
	if(!y)
		return x;
	return gcd(y,x%y);
}

int main() {
	for( int i = 2 ; i < maxn ; i++ )
		if(primes[i].empty())
			for( int j = i ; j < maxn ; j += i )
				primes[j].pb(i);
	scanf("%d",&n);
	bool isCoprime = true;
	for( int i = 0 , x ; i < n ; i++ ) {
		scanf("%d",&x);
		int p = primes[x].size();
		for( int j = 0 ; j < p ; j++ ) {
			int num = primes[x][j];
			if(var[num])
				isCoprime = false;
			else
				var[num] = true;
		}
		if(i == 0)
			g = x;
		else
			g = gcd(g,x);
	}
	if(isCoprime)
		puts("pairwise coprime");
	else if(g == 1)
		puts("setwise coprime");
	else
		puts("not coprime");
	return 0;
}

Measured memory_bytes: 60068
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<functional>
#include<iomanip>
using namespace std;

#define INF 1<<21
#define DIV 1000000007

int main() {
  string s;
  bool k = false;
  cin >> s;
  int n = s.length();
  char c;
  for (c = 'a'; c <= 'z'; c++) {
	bool b = false;
	for (int i = 0; i < n; i++) {
	  if (s[i] == c)b = true;
	}
	if (!b) {
	  k = true;
	  cout << c << endl;
	  break;
	}
  }
  if (!k)cout << "None" << endl;
}

Measured memory_bytes: 512
from collections import deque
n, m = list(map(int, input().split()))
path = {}
ab = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    a, b = ab[i]
    if not a in path.keys():
        path[a] = [b]
    else:
        path[a].append(b)
    if not b in path.keys():
        path[b] = [a]
    else:
        path[b].append(a)

ans = 0
for i in range(m):
    a_tar, b_tar = ab[i]
    visit = [True] + [False]*n
    que = deque([1])
    while len(que) > 0:
        node = que.popleft()
        visit[node] = True
        for node_next in path[node]:
            if [node, node_next] == [a_tar, b_tar] or [node, node_next] == [b_tar, a_tar]:
                continue
            if visit[node_next]:
                continue
            que.append(node_next)
    if False in visit:
        ans += 1
print(ans)


Measured memory_bytes: 3316
#include <stdio.h>
#include <algorithm>

int main(void)
{

    while(true) {
        int a[100], b[100], sa=0, sb=0, c, n, m;
        int ans[2]={-1, -1};

        scanf("%d%d", &n, &m);
        if(n==0 && m==0) break;

        for(int i=0; i < n; i++)
            scanf("%d", &a[i]), sa += a[i];
        for(int i=0; i < m; i++)
            scanf("%d", &b[i]), sb += b[i];

        std::sort(a, a+n);
        std::sort(b, b+m);

        c = sa - sb;

        for(int i=0; i < n && ans[0] == -1; i++)
        {
            if(c%2) break;

            if(*std::lower_bound(b, b + m, a[i] - c/2) == a[i]-c/2)
                ans[0] = a[i], ans[1] = a[i]-c/2;
        }

        if(ans[0] == -1)
            printf("-1\n");
        else
            printf("%d %d\n", ans[0], ans[1]);


    }

    return 0;
}

Measured memory_bytes: 1056
import java.io.*;

public class Main {
	public static void main(String[] args) {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try {
			int a = Integer.parseInt(reader.readLine());
			int b = Integer.parseInt(reader.readLine());
			int h = Integer.parseInt(reader.readLine());
			System.out.println((a + b) * h / 2);
		} catch(IOException e) {
			System.out.println(e);
		}
		
		
	}

}


Measured memory_bytes: 21076
import java.util.*;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt(); //a個口の電源タップ
		int aa = a-1; //aの値保管用
		
		int b = stdIn.nextInt(); //b以上に拡張したい
		int count = 1; //電源タップの数のカウント
		
		if(b==1){
			System.out.println(0);
			System.exit(0);
		}
		
		if(a>=b){
			System.out.println(count);
			System.exit(0);
		}
		
		do{
			a+=aa;
			count++;
		}while(a<b);
		
		System.out.println(count);
		stdIn.close();
		
		
		
		
		
	}

}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;

int main()
{
	int k;
	cin>>k;
	while(k--){
		cout<<"ACL";
	}
	cout<<endl;
//cout<<int('#')<<endl;
//cout<<char(int('#'));
 return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision(10) << num << endl;
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    string s; cin >> s;
    int n=s.size();
    int dp[n+1][2];
    dp[0][0]=0;
    dp[0][1]=1;
    rep(i,n){
        int x=s[i]-'0';
        dp[i+1][0]=min(dp[i][0]+x,dp[i][1]+10-x);
        dp[i+1][1]=min(dp[i][0]+x+1,dp[i][1]+9-x);
    }
    cout << dp[n][0] << endl;
}




Measured memory_bytes: 9220
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
l=[]
for i in range(n):
    l.append([a[i],1+i])
l=sorted(l,key=lambda x:x[0])
ans=[]
for i in range(n):
    ans.append(l[i][1])
print(*ans)

Measured memory_bytes: 107232
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1E9 + 7;
const int INF = 1 << 29;

int main() {
  ll N;
  cin >> N;
  ll count = 1;
  ll ans = 0;
  while (count <= N) {
    if ((count % 3 != 0) && (count % 5 != 0)) {
      ans += count;
    }
    count += 1;
  }
  cout << ans << endl;
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<60;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

ll n, k;
vll a;
vll aminus, aplus;
ll minu = 0, zero = 0, plu = 0;

bool ok1 (ll mid1, bool pl) {
  ll cnt = 0;
  if(pl) {
    for(int i=0;i<SZ(aminus);++i) {
      ll l2 = i, r2 = SZ(aminus);
      while(r2 - l2 > 1) {
        ll mid2 = (l2 + r2) / 2;
        //cout << aminus[i] << " " << aminus[mid2] << endl;
        if(aminus[i] * aminus[mid2] <= mid1) l2 = mid2;
        else r2 = mid2;
      }
      //cout << i << ":" << l2 << endl;
      cnt += l2 - i;
    }
    for(int i=0;i<SZ(aplus);++i) {
      ll l2 = i, r2 = SZ(aplus);
      while(r2 - l2 > 1) {
        ll mid2 = (l2 + r2) / 2;
        if(aplus[i] * aplus[mid2] <= mid1) l2 = mid2;
        else r2 = mid2;
      }
      //cout << i << ":" << l2 << endl;
      cnt += l2 - i;
    }
  } else {
    for(int i=0;i<SZ(aminus);++i) {
      ll l2 = -1, r2 = SZ(aplus);
      while(r2 - l2 > 1) {
        ll mid2 = (l2 + r2) / 2;
        if(aminus[i] * aplus[mid2] > mid1) l2 = mid2;
        else r2 = mid2;
      }
      //if(mid1 == -13) cout << i << ":" << r2 << endl;
      cnt += SZ(aplus) - r2;
    }
  }
  //cout << mid1 << " " << cnt << endl;

  return cnt < k;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  cin >> n >> k;
  a.resize(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
    if(a[i] < 0) {
      minu++;
      aminus.push_back(a[i]);
    } else if(a[i] == 0) {
      zero++;
    } else {
      plu++;
      aplus.push_back(a[i]);
    }
  }

  zero = zero * (zero - 1) / 2 + zero * (n - zero);
  ll minustmp = minu * plu;
  plu = minu * (minu - 1) / 2 + plu * (plu - 1) / 2;
  minu = minustmp;

  
  bool pl = false;  

  ll l1 = -LINF, r1 = LINF;
  if(minu + zero < k) {
    pl = true;
    k -= minu + zero;
    sort(aminus.rbegin(), aminus.rend());
    sort(aplus.begin(), aplus.end());
  } else if(minu < k) {
    cout << 0 << endl;
    return 0;
  } else {
    sort(aminus.begin(), aminus.end());
    sort(aplus.begin(), aplus.end());
  }

  //printv(aminus);
  //printv(aplus);

  
  while(r1 - l1 > 1) {
    ll mid1 = (l1 + r1) / 2;

    if(ok1(mid1, pl)) {
      l1 = mid1;
    } else {
      r1 = mid1;
    }
  }
  
  //cout << k << endl;
  cout << l1 + 1 << endl;

}


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

if abs(N - M) >= 2:
    print(0)

elif N == M:
    ans = 1
    for i in range(1,N+1):
        ans = (ans * i) % (10 ** 9 + 7)
    for i in range(1, M + 1):
        ans = (ans * i) % (10 ** 9 + 7)
    print((2 * ans) % (10 ** 9 + 7))
else:
    ans = 1
    for i in range(1,N+1):
        ans = (ans * i) % (10 ** 9 + 7)
    for i in range(1, M + 1):
        ans = (ans * i) % (10 ** 9 + 7)
    print(ans % (10 ** 9 + 7))

    

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

#define ll long long int

void solve(){
    ll n,k;
    cin >> n >> k;
    vector<ll> v(n);
    for(auto &it:v)
        cin >> it;
    sort(v.begin(),v.end());
    if(k >= n){
        cout << 0 << '\n';
        return;
    }

    ll sum=0;
    for(int i=0;i<n-k;i++)
        sum += v[i];
    cout << sum << '\n';
}

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

    int test=1;
    // cin >> test;
    while(test--)
        solve();
    
    return 0;
}

Measured memory_bytes: 1792
# D
H, W, N = map(int,input().split())
field_dict = dict()
X_list = [0]*N
Y_list = [0]*N

for i in range(N):
    X, Y = map(int,input().split())
    X_list[i] = X-1
    Y_list[i] = Y-1
    field_dict[(X-1)*1000000 + (Y-1)] = 1

def query(posi_x, posi_y):
    return field_dict.get(posi_x*1000000+posi_y, 0)

# minimam x reachable
reach_y = [H]*W
reach_y[0] = 0
posi_x, posi_y = 0, 0

while posi_x < H - 1:
    # takahashi
    if query(posi_x+1, posi_y) == 1:
        # gameover
        break
    else:
        posi_x += 1
    # aoki
    if query(posi_x, posi_y+1) == 0 and posi_y + 1 < W:
        # move
        posi_y += 1
        reach_y[posi_y] = posi_x
        
res = H

for i in range(N):
    if reach_y[Y_list[i]] < X_list[i]:
        res = min(res, X_list[i])
        
print(res)

Measured memory_bytes: 44680
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
using namespace std;
int n;
vector<string> v;
map<string,int> m;

int main() {
    cin>>n;
    string s;
    bool f=true;
    for (int i=0;i<n;i++) {
        cin>>s;
        v.push_back(s);
        if (v.size()>1 && s[0] != v[v.size()-2][v[v.size()-2].length()-1])
        {
            f=false;
            break;
        }
        if (m.find(s)!=m.end()) {
            f=false;
            break;
        }
        m[s]++;
    }
    printf("%s\n", f ? "Yes" : "No");
    return 0;
}


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

int main()
{
   int arr[5],k,x;
   for(int i=0;i<5;i++){
    scanf("%d",&arr[i]);
   }
    scanf("%d",&k);
   for(int i=4;i>0;i--){
    for(int j=0;j<i;j++){
        x=(arr[i]-arr[j]);
        if(x>k){
            printf(":(");
            return 0;
        }
    }
   }
   printf("Yay!");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,a[100005];
int val[100005];
int main(){
	scanf("%d",&n);
	rep(i,n) scanf("%d",&a[i]);
	val[0] = -1;
	for(int i=1;i<100005;i++) val[i] = INF+4;
	for(int i=n-1;i>=0;i--){
		int b = upper_bound(val,val+100005,a[i])-val;
		val[b] = a[i];
	}
	for(int i=100001;i>=0;i--){
		if(val[i] != INF+4) {cout<<i<<endl;return 0;}}
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>

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

using namespace std;
using ll = long long;


int main() {

	int d;
	ll g;
	cin >> d >> g;

	vector<int> p(10);
	vector<ll> c(10);
	ll ans = 100000000;

	REP(i, d) {
		cin >> p[i] >> c[i];
	}
	FOR(i, d, 10) {
		p[d] = 0;
		c[d] = 0;
	}

	for (int i = 0; i < 2048; i++) {
		int t = i;
		ll v = 0;
		vector<int> dd(10, 0);
		ll cand = 0;
		for (int j = 0; j < 10; j++) {
			if (t & 0b1) {
				v += p[j] * (j + 1) * 100 + c[j];
				cand += p[j];
				dd[j] = 1;
			} 
			t = t >> 1;
		}
		if (v >= g) {
			ans = min(ans, cand);
			goto exit;
		}
		for (int j = 9; j >= 0; j--) {
			if(dd[j] == 0)
			for (int k = 1; k <= p[j]; k++) {
				v += (j + 1) * 100;
				cand++;
				if (v >= g) {
					ans = min(ans, cand);
					goto exit;
				}
			}
		}
	exit:;
	}


	cout << ans NL;

	return 0;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair <int,vector<int> > P;

static const double eps = 1e-8;

int visited[15000000];

int conv(vector<int>& sets){
	int res = 0;
	for(int i=0;i<sets.size();i++){
		for(int j=0;j<=15;j++){
			if(sets[i] & (1<<j)){
				res += i * (pow(3.0,j)+eps);
			}
		}
	}
	return res;
}

int bfs(int m,vector<int>& root, int* visited){

	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,root));
	visited[conv(root)] = 0;
	vector<int> tmp;
	vector<int> sets;
	while(!que.empty()){
		int cost = que.top().first;
		
		sets = que.top().second;

		if(sets[1]==0 && sets[2]==0) return cost;
		if(sets[0]==0 && sets[1]==0) return cost;

		if(cost >= m) break;
		que.pop();
		for(int i=0;i+1<sets.size();i++){
			if((sets[i] && sets[i+1] && sets[i] < sets[i+1]) 
				|| (!sets[i] && sets[i+1])){
				tmp = sets;

				int pos=0;
				for(int j=15;j>=0;j--){
					if(tmp[i+1] & (1<<j)){
						pos = j;
						break;
					}
				}
				tmp[i+1] &= ~(1<<pos);
				tmp[i] |= (1<<pos);

				
				int next;
				if(visited[(next = conv(tmp))] == -1){
					visited[next] = cost+1;
					que.push(P(cost+1,tmp));
				}
			}

			else if((sets[i] && sets[i+1] && sets[i] > sets[i+1]) 
				|| (sets[i] && !sets[i+1])){
				tmp = sets;

				int pos=0;
				for(int j=15;j>=0;j--){
					if(tmp[i] & (1<<j)){
						pos = j;
						break;
					}
				}
				tmp[i] &= ~(1<<pos);
				tmp[i+1] |= (1<<pos);

				int next;
				if(visited[(next = conv(tmp))] == -1){
					visited[next] = cost+1;
					que.push(P(cost+1,tmp));
				}
			}
		}
	}
	return -1;
}

int main(){

	int n,m;
	while(~scanf("%d %d",&n,&m)){
		if(n==m && m==0) break;
		vector<int> sets(3);
		memset(visited,-1,sizeof(visited));
		for(int i=0;i<3;i++){
			int amount;
			scanf("%d",&amount);
			for(int j=0;j<amount;j++){
				int size;
				scanf("%d",&size);
				sets[i] |= (1<<(size-1)); 
			}
		}

		printf("%d\n",bfs(m,sets,visited));
	}
}

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

int main(){

int N,i;
scanf("%d",&N);

if(N < 1||N > 200){
exit(1);
}

if(N >= 1&&N <= 104)
i = 0;
if(N >= 105&&N <= 134)
i = 1;
if(N >= 135&&N <= 164)
i = 2;
if(N >= 165&&N <= 188)
i = 3;
if(N >= 189&&N  <= 194)
i = 4;
if(N >= 195&& N <= 200)
i = 5;

printf("%d",i);
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : "\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    int n;
    cin>>n;
    vi a(n);
    cin>>a;
    if(n<=2) {
        cout<<1<<endl;
        return 0;
    }

    int ans=1;
    int i=1;
    bool increase;
    while(a[i-1]==a[i]) {
        i++;
        if(i==n) goto end;
    }
    increase=a[i-1]<a[i];
    for(i=1;i<n;++i) {
        if(a[i-1]==a[i]) continue;
        if(increase != (a[i-1]<a[i])) {
            ans++;
            i++;
            if(i==n) goto end;
            while(a[i-1]==a[i]) {
                i++;
                if(i==n) goto end;
            }
            increase=a[i-1]<a[i];
        }
    }
    end:;
    cout<<ans<<endl;
    return 0;
}


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

int main(){
  string s,t;
  cin >>s >>t;
  bool reason=false;
  for(int i=s.size()-t.size();i>=0;i--){
    bool ok=true;
    for(int j=t.size()-1;j>=0;j--){
      if(s[i+j]!='?'){
        if(s[i+j]!=t[j])ok=false;
      }
    }
    if(ok){
      for(int j=0;j<t.size();j++)s[i+j]=t[j];
      for(int j=0;j<s.size();j++)
        if(s[j]=='?')s[j]='a';
      reason=true;
      break;
    }
  }
  if (!reason) cout << "UNRESTORABLE" <<endl;
  else cout << s <<endl;
}

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

#define ll long long 
#define ff(i, a, b) for(int i = a; i <= b; i++)
#define fo(i, a, b) for(int i = a; i < b; i++)
#define fod(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int INF = 1e9, N = 1010;
const ll INFL = 1e18;

typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

int n, m, f[N][N], ans, res;
char a[N][N];
char c[3][3];

int in(int x, int y) {
	return (x >= 1 && x + 1 <= n && y >= 1 && y + 1 <= m);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; ff(i, 1, n) ff(j, 1, m) cin >> a[i][j];
	ff(i, 1, 2) ff(j, 1, 2) cin >> c[i][j];
	ff(i, 0, n - 1) ff(j, 0, m - 1) {
		int x = i + 2, y = j + 2;
		ff(I, i, x - 1) ff(J, j, y - 1) {
			if (!in(I, J)) continue;
			if (a[I][J] == c[1][1] && a[I][J + 1] == c[1][2] && a[I + 1][J] == c[2][1] && a[I + 1][J + 1] == c[2][2]) f[i+1][j+1]++;
		} 
		//cout << i + 1 << ' ' << j + 1 << ' ' << f[i + 1][j + 1] << "\n";
	}
	ff(i, 1, n - 1) ff(j, 1, m - 1) {
		if (a[i][j] == c[1][1] && a[i][j + 1] == c[1][2] && a[i + 1][j] == c[2][1] && a[i + 1][j + 1] == c[2][2]) ans++;
	}
	res = ans;
	ff(x, 1, 2) ff(y, 1, 2) {
		// cut in the square (x, y) of 2x2 square
		char cur = c[x][y];
		ff(i, 1, n) ff(j, 1, m) {
			char k = a[i][j];
			a[i][j] = cur;
			int cnt = 0;
			ff(I, i - 1, i) ff(J, j - 1, j) {
				if (!in(I, J)) continue;
				if (a[I][J] == c[1][1] && a[I][J + 1] == c[1][2] && a[I + 1][J] == c[2][1] && a[I + 1][J + 1] == c[2][2]) cnt++;
			}
			int Ans = ans - f[i][j] + cnt;
			res = max(res, Ans);
			a[i][j] = k;
		}
	}
	printf("%d\n", res);
}

Measured memory_bytes: 6140
#[allow(unused)]
use std::io::Write;
use std::collections::{HashMap, HashSet};

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn main() {
    let n: usize = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right().to_owned();
        s.parse().unwrap()
    };

    let divs = divisors(n);
    let mut min = std::usize::MAX;
    for d in divs {
        let tmp = d + n / d - 2;
        if tmp < min {
            min = tmp
        }
    }
    println!("{}", min);
}

fn prime_sieve(n: usize) -> Vec<usize> {
    let mut table: Vec<usize> = vec![0; (n + 1) as usize];
    let mut primes: Vec<usize> = Vec::new();

    for i in 2..(n+1) {
        if table[i as usize] == 0 {
            primes.push(i);
            for j in 2..n {
                if i * j > n {
                    break
                }
                table[(i * j) as usize] = 1
            }
        }
    }

    primes
}

fn prime_factor(n: usize) -> HashMap<usize, usize> {
    let mut factors = HashMap::new();

    let primes = prime_sieve((n as f64).sqrt() as usize);
    let mut rest = n;
    for p in primes {
        while rest % p == 0 {
            let count = factors.entry(p).or_insert(0);
            *count += 1;
            rest /= p;
        }
    }
    if rest != 1 {
        factors.insert(rest, 1);
    }

    factors
}

fn divisors(n: usize) -> HashSet<usize> {
    let mut set = HashSet::new();
    set.insert(1);

    prime_factor(n).iter().fold(set, |acc, (&p, &pow)| {
        (0..pow+1).flat_map(|i| acc.iter().map(move |a| a * p.pow(i as u32))).collect()
    })
}


Measured memory_bytes: 12540
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void) {
	
	int lh,lw,sh,sw;
	cin >>lh >>lw >>sh >>sw;
	
	int ans=(lh*lw)-(sh*lw)-(sw*lh)+(sw*sh);
	cout <<ans <<endl;
	
	return 0;
}

Measured memory_bytes: 256
#good grid
n,c=map(int,input().split())
mod1=[]
mod2=[]
mod3=[]
change=[0 for j in range(c)]
for i in range(c):
    change[i]=list(map(int,input().split()))
    
for i in range(n):
    s=list(map(int,input().split()))
    for some in range(n):
        if (((some+1)+(i+1))%3)==0:
            mod3.append(s[some])
        if (((some+1)+(i+1))%3)==1:
            mod1.append(s[some])
        if (((some+1)+(i+1))%3)==2:
            mod2.append(s[some])
change_to_some=[[0 for i in range(c)]  for k in range(3)]
for j in range(c):
    a=0
    for k in (mod1):
        a+=change[k-1][j]
    change_to_some[0][j]=a
for j in range(c):
    a=0
    for k in (mod2):
        a+=change[k-1][j]
    change_to_some[1][j]=a
for j in range(c):
    a=0
    for k in (mod3):
        a+=change[k-1][j]
    change_to_some[2][j]=a

anslist=[]
for a in range(c):
    for b in range(c):
        for k in range(c):
            if a!=b and b!=k and a!=k:
                anslist.append(change_to_some[0][a]+change_to_some[1][b]+change_to_some[2][k])
print(min(anslist))

Measured memory_bytes: 6072
#include<iostream>
#include<string>
#include<vector>
#define int long long
using namespace std;
signed main(void){
    int n,a,mxa=0,ans=0;
    cin>>n;
    while(cin>>a){
        if(a>=mxa)
            mxa=a;
        else
            ans+=mxa-a;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include<string.h>
#include<stdio.h>

char input[10002];
int slen;

int main(){
	int i;
	while( scanf("%s",input) != EOF ){
		slen = strlen(input);
		int cnt_joi = 0;
		int cnt_ioi = 0;
		for( i = 0; i < slen; i++ ){
			if( input[i] == 'J' && input[i+1] == 'O' && input[i+2] == 'I' ){
				cnt_joi++;
			}
			if( input[i] == 'I' && input[i+1] == 'O' && input[i+2] == 'I' ){
				cnt_ioi++;
			}
		}
		printf("%d\n%d\n",cnt_joi,cnt_ioi);
	}			
	return 0;
}

Measured memory_bytes: 976
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    string s;
    cin >> s;
    string x, y;
    x.push_back(s[0]), x.push_back(s[1]);
    y.push_back(s[2]), y.push_back(s[3]);
    int X = stoi(x); int Y = stoi(y);
    if (X > 12) {
        if (Y == 0) cout << "NA" << endl;
        else if (Y <= 12) cout << "YYMM" << endl;
        else cout << "NA" << endl;
    }
    else {
        if (X == 0) {
            if (Y <= 12 && Y > 0) cout << "YYMM" << endl;
            else cout << "NA" << endl;
        }
        else if (Y == 0) cout << "MMYY" << endl;
        else if (Y > 12) cout << "MMYY" << endl;
        else cout << "AMBIGUOUS" << endl;
    }
    return 0;
}

Measured memory_bytes: 256