akhauriyash/Code-Regression huggingface dataset:
#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long

int a[300000];
_int64 sum[300000];
vector<_int64> aa; 
map<_int64,int> mp;
int d[500000];

int lowbit(int x)
{
  return (x&(x-1))^x;
}

void add1(int x)
{
  int i;
  for (i=x;i<500000;i+=lowbit(i))
    d[i]++;
}

int getn(int x)
{
  int i,ret;
  ret=0;
  for (i=x;i>0;i-=lowbit(i))
    ret+=d[i];
  return ret;
}

int main()
{
  int i,n,k,tmp;
  _int64 ans;
  scanf("%d%d",&n,&k);
  for (i=0;i<n;i++)
  {
    scanf("%d",&a[i]);
    a[i]-=k;
  }
  sum[0]=0;
  for (i=0;i<n;i++)
    sum[i+1]=sum[i]+a[i];
  aa.clear();
  for (i=0;i<=n;i++)
    aa.push_back(sum[i]);
  sort(aa.begin(),aa.end());
  aa.erase(unique(aa.begin(),aa.end()),aa.end());
  mp.clear();
  for (i=0;i<aa.size();i++)
    mp[aa[i]]=i+1;
  ans=0;
  memset(d,0,sizeof(d));
  for (i=0;i<=n;i++)
  {
    tmp=mp[sum[i]];
    ans+=getn(tmp);
    add1(tmp);
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 19184
#include <iostream>
#include <string>
#include <unordered_map>
#define int long long
using namespace std;
int n;
unordered_map<string,int> h_m;
signed main(){
    string word;
    int m_len = 0, m_count = 0;
    string w_len = "", w_count = "";
    while(cin >> word){
        h_m[word] += 1;
        if(m_len < word.size()){
            m_len = word.size();
            w_len = word;
        }
        if(m_count < h_m[word]){
            m_count = h_m[word];
            w_count = word;
        }
    }
    cout << w_count << " " << w_len << endl;
}


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

int main(){
	int a,b,x;cin>>a>>b>>x;
	x=(x+499)/500*500;
	if(x%1000==0){
		cout<<min(a,b*2)*(x/1000)<<endl;
	}
	else{
		cout<<min({(x/1000+1)*a,(x/500)*b,(x/1000)*a+b})<<endl;
	}
}



Measured memory_bytes: 3084
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>
 
using namespace std;
 
#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1};
 
const ll INF = LLONG_MAX/2;
 
int main() {
    int town_n, order_n;
    while(cin >> town_n >> order_n, town_n|order_n){
        vvll E_stk(town_n, vll(town_n, INF));
        vvll E(town_n, vll(town_n, INF));
 
        int order, from, to, cost;
        bool made = true;
        REP(i, order_n){
            cin >> order;
            if(!order){
                if(!made){
                    E = E_stk;
                    made = true;
                    REP(i, town_n) REP(j, town_n) REP(k, town_n){
                        E[j][k] = E[j][k] < E[j][i] + E[i][k] ? E[j][k] : E[j][i] + E[i][k];
                    }
                }
                cin >> from >> to;
                from--; to--;
                cout << (E[from][to] == INF ? -1 : E[from][to]) << endl;
            }else{
                made = false;
                cin >> from >> to >> cost;
                from--; to--;
                E_stk[from][to] = cost < E_stk[from][to] ? cost : E_stk[from][to];
                E_stk[to][from] = cost < E_stk[to][from] ? cost : E_stk[to][from];
            }
        }
    }
}

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	ll x;
	ll ans = 0;
	cin >> x;

	ll div = x / 11;
	ans += div*2;
	x -= div*11;

	div = x / 6;
	x -= div*6;
	ans += div;
	if(x > 0) ans++;

	cout << ans << endl;

	
	return 0;
}


Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))

cnt = 0

for i in range(1, n-1):
    if p[i-1] < p[i] and p[i] < p[i+1]:
        cnt += 1
    elif p[i-1] > p[i] and p[i] > p[i+1]:
        cnt += 1

print(cnt) 

Measured memory_bytes: 3060
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll n;
    cin >> n;
    vector<ll> A(n);
    rep(i, n) cin >> A[i];

    vector<ll> S(n+1);
    rep(i, n) S[i+1] = i == 0 ? A[0] : S[i] + A[i];

    ll res = 1e18;
    for(int i = 2; i <= n; i++) {
        // [0,i), [i,n)を二分かつ
        auto it1 = lower_bound(S.begin(), S.begin() + i, S[i-1]/2);
        auto i1 = it1 - S.begin();
        auto it2 = lower_bound(S.begin()+i, S.end(), (S[n]-S[i-1])/2 + S[i-1]);
        auto i2 = it2 - S.begin();

        for (int j = i1-2; j <= i1+2; j++) {
            for (int k = i2-2; k <= i2+2; k++) {
                if (j <= 1 || i - j <= 0 || k - i <= 0 || k >= n+1) {
                    continue;
                }
                // j, i, kで切る
                ll P = S[j-1];
                ll Q = S[i-1] - S[j-1];
                ll R = S[k-1] - S[i-1];
                ll Z = S[n] - S[k-1];
                ll mi = min(P, min(Q, min(R, Z)));
                ll ma = max(P, max(Q, max(R, Z)));
                ll diff = ma - mi;
                res = min(res, diff);
            }
        }
    }

    put(res);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 6404
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int MOD = (int)998244353;
const int kN = 4000 + 5;
int Inv[kN], Finv[kN], F[kN];
int pw2[kN];

int binom(int a, int b) {
  if (b < 0 || b > a) return 0;
  return F[a] * 1LL * Finv[b] % MOD * Finv[a - b] % MOD;
}

int calc(int n, int k, int ban) {
  int r = k - 2 * ban;
  int ret = 0;
  for (int i = 0; i <= ban && i <= n; ++ i) {
    (ret += pw2[i] * 1LL * binom(n - i + r + i - 1, r + i - 1) % MOD * binom(ban, i) % MOD) %= MOD;
  }
  return ret;
}

int solve(int n, int k, int ban, int single) {
  int ret = 0;
  for (int w = 0; w <= single; ++ w) {
    (ret += calc(n - w, k - single, ban)) %= MOD;
  }
  return ret;
}

int main() {
  pw2[0] = 1;
  for (int i = 1; i < kN; ++ i)
    pw2[i] = pw2[i - 1] * 1LL * 2 % MOD;
  Inv[1] = 1;
  for (int i = 2; i < kN; ++ i)
    Inv[i] = (MOD - MOD / i) * 1LL * Inv[MOD % i] % MOD;
  F[0] = Finv[0] = 1;
  for (int i = 1; i < kN; ++ i) {
    F[i] = F[i - 1] * 1LL * i % MOD;
    Finv[i] = Finv[i - 1] * 1LL * Inv[i] % MOD;
  }
  int n, k;
  scanf("%d%d", &k, &n);
  for (int i = 2; i <= 2 * k; ++ i) {
    int ban = 0, single = 0;
    for (int j = 1; j <= k; ++ j) {
      int r = i - j;
      if (j <= r && r >= 1 && r <= k) {
        if (j == r)
          ++ single;
        else
          ++ ban;
      }
    }
    printf("%d\n", solve(n, k, ban, single));
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

class UnionFind {
public:
  vector<ll> par;
  vector<ll> siz;
  
  UnionFind(ll sz_) : par(sz_), siz(sz_, 1) {
    for(int i = 0; i < sz_; i++) par[i] = i;
  }
  
  void init(ll sz_){
    par.resize(sz_);
    siz.assign(sz_, 1);
    for (ll i = 0; i < sz_; ++i) par[i] = i;
  }
  
  ll root(ll x){
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  
  bool unite(ll x, ll y){
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }
  
  bool same(ll x, ll y){
    return root(x) == root(y);
  }
    
  ll size(ll x){
    return siz[root(x)];
  }
};

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> fri(n), blo(n);
  UnionFind tree(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--, b--;
    fri[a].push_back(b);
    fri[b].push_back(a);
    tree.unite(a, b);
  }
  rep(i, k){
    int c, d;
    cin >> c >> d;
    c--, d--;
    blo[c].push_back(d);
    blo[d].push_back(c);
  }
  
  rep(i, n){
    int ans = tree.size(i) - 1;
    ans -= fri[i].size();
    for(j : blo[i]){
      if (tree.same(i, j)) ans--;
    }
    cout << ans;
    if(i == n-1) cout << endl;
    else cout << ' ';
  }
  
  return 0;
}


Measured memory_bytes: 13432
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = B[:] + [0]

for i in range(N)[::-1]:
    remain = A[i + 1] - ans[i + 1]
    if remain > 0:
        ans[i], ans[i + 1] = max(0, ans[i] - remain), min(ans[i + 1] + ans[i], A[i + 1])
    else:
        ans[i + 1] = A[i + 1]
ans[0] = min(ans[0],A[0])
print(sum(ans))



Measured memory_bytes: 18624
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        string s;
        cin >> s;
        for(auto &it : s){
            if(it == '?'){
                it = 'D';
            }
        }
        cout << s << '\n';
    }
}

Measured memory_bytes: 34888
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

string n;
ll k, dp[101][4][2] = {};

int main() {
	cin >> n;
	cin >> k;
	dp[0][0][0] = 1;
	rep(i, sz(n)) {
		rep(j, k + 1) {
			rep(l, 10) {
				if (l == 0) {
					dp[i + 1][j][1] += dp[i][j][1];
					if (n[i] == '0') {
						dp[i + 1][j][0] += dp[i][j][0];
					}
					else {
						dp[i + 1][j][1] += dp[i][j][0];
					}
				}
				else if (j < k) {
					dp[i + 1][j + 1][1] += dp[i][j][1];
					if (l == n[i] - '0') dp[i + 1][j + 1][0] += dp[i][j][0];
					if (l < n[i] - '0') dp[i + 1][j + 1][1] += dp[i][j][0];
				}
			}
		}
	}
	cout << dp[sz(n)][k][0] + dp[sz(n)][k][1] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string x,y;
  cin>>x>>y;
  int u=0;
  for(int i=0;i<3;i++){
    if(x[i]==y[2-i])u++;
  }
  if(u==3)cout<<"YES";
  else cout<<"NO";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
#define vvll vector<vector<long long>>
using namespace std;
using ll = long long;
using ld = long double;

// グローバル変数（入力）
ll x,n,maxP;
vll p;

void input() { 
  cin >> x >> n;
  maxP = 0;
  rep(i,n){
    ll P; cin >> P;
    maxP = max(maxP,P);
    p.push_back(P);
  }
}

ll solve() {
  vll a(maxP+2,0);
  rep(i,n){
    a[p[i]]=1;
  }
  ll lOver=0;
  ll rOver=0;
  rep(i,max(maxP-x,x)){
    if (x-i>=0){
      if (a[x-i]==0){
        cout << x-i << endl;
        return 0;
      }
    } else {
      lOver++;
    }

    if (x+i<=maxP+1){
      if (a[x+i]==0){
        cout << x+i << endl;
        return 0;
      }
    } else {
      rOver++;
    }
  }
  if (lOver>=rOver){
    cout << 0 << endl;
  } else {
    cout << maxP+1 << endl;
  }

  return 0;
  
}

int main() {
  input();
  solve();
  return 0;
}


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

int main(){
    int A, B, C;
    int flag = 0;
    cin >> A >> B >> C;
    if(A == B && B != C){
        flag = 1;
    }
    if(B == C && A != B){
        flag = 1;
    }
    if(A == C && A != B){
        flag = 1;
    }
    
    if(flag == 1){
        cout << "Yes" << endl;
    }
    if(flag == 0){
        cout << "No" << endl;
    }

    return 0;
}


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

int main()
{
    int N;
    cin >> N;

    set<int> st;    
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        bool has_a = st.erase(a);
        if (!has_a)
        {
            st.insert(a);
        }
    }

    cout << st.size() << endl;

    return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define ll long long

using namespace std;

constexpr int ms = 3013;

ll dp[ms][ms];
bool seen[ms][ms];

void solve() {
    int n;
    cin >> n;

    vector<ll> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];

    memset(dp, 0, sizeof(dp));
    memset(seen, false, sizeof(seen));

    function<ll(int, int)> calc_dp = [&] (int i, int j) {
        if (i > j) {
            return 0ll;
        }
        if (seen[i][j]) {
            return dp[i][j];
        }

        dp[i][j] = max(v[i] - calc_dp(i+1, j), v[j] - calc_dp(i, j-1));
        seen[i][j] = true;

        return dp[i][j];
    };

    cout << calc_dp(0, n-1) << endl;
}

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

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
    // cin >> t;

    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 83808
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  long long n, m, l, b[100][100], a[100][100], c[100][100] = {};
  cin >> n >> m >> l;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 0; i < m; i++){
    for(int j = 0; j < l; j++){
      cin >> b[i][j];
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      for(int k = 0; k < l; k++){
        c[i][k] += a[i][j] * b[j][k];
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < l; j++){
      cout << (j == 0 ? "": " ") << c[i][j];
    }
    cout << endl;
  }
}


Measured memory_bytes: 3324
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	int a, b, c, d, e, f;
	while(cin >> a >> b >> c >> d >> e >> f) {
		DEBUG(f);
		vector<vector<bool>> dp(f+1, vector<bool>(f+1, false));
		dp[0][0] = true;
		REP(i,f+1) {
			REP(j, f+1){
				if(i == 0 and j == 0) continue;
				bool x = false;
				if(i-c >= 0 and j-c >= 0) x = x or dp[i-c][j-c];
				if(i-d >= 0 and j-d >= 0) x = x or dp[i-d][j-d];
				if(j-100*a >= 0) x = x or dp[i][j-100*a];
				if(j-100*b >= 0) x = x or dp[i][j-100*b];
				dp[i][j] = x;
			}
		}
		// REP(i, f+1) dpite(ALL(dp[i]));
		double ans = -1;
		int hoge = 0;
		int fuga = 0;
		double maxno = (double)e/(100+e);
		REP(i,f+1) REP(j,f+1){
			if(dp[i][j]){
				DEBUG(i); DEBUG(j);
				double x = (double)i/j;
				DEBUG(maxno);
				DEBUG(x);
				if(x <= maxno) {
					DEBUG(i); DEBUG(j); DEBUG(x);
					if(chmax(ans, x)){
						hoge = i;
						fuga = j;
					}
				}
			}
		}
		cout << fuga << ' ' << hoge << endl;
	}
	return 0;
}


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

int main(){

    int a; cin >> a;
    int b; cin >> b;

    /******************************************************
    if(a <= (b*2)){
        cout << 0 << endl;
    }else{
        cout << a - (b * 2) << endl; 
    }
    ******************************************************/

    ///****************************
    //[max関数を使おう！！]
    int ans;
    ans = max(0 , a - (b * 2));
    cout << ans << endl;
    //****************************/

    return 0;
}

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

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	string S;
	cin >>S;
	string s="CODEFESTIVAL2016";
	int n=0;
	Rep0(i, S.size())
		if (S.at(i)!=s.at(i))
			n++;
	cout <<n <<endl;
	return 0;
}



Measured memory_bytes: 256
#include<algorithm>//sort(all(変数),greater<型名>())で降順に、*max_element(all(変数))で最大値を獲得
#include<bits/stdc++.h>
#include<cmath>//切り上げceil(値)
#include<deque>
#include<iomanip>//setprecision(数字)
#include<iostream>
#include<list>
#include<map>
#include<numeric>
//xとyのgcdは__gcd(x,y),xとyのlcmは(x*y)/__gcd、accumulate(all(変数),0)で要素の全加算
#include<queue>//priority_queue<型名> 変数
#include<set>
#include<stack>
#include<string>
#include<vector>
#define rep(i,n)  for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; 0<=i; i--)
#define vll vector<ll>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF 1e18
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
  int n; cin >> n;
  vi a(n); rep(i,n) cin >> a[i];
  vi check(n-1);
  rep(i,n-1) check[i] = a[i+1]-a[i];
  vector<bool> increase;
  rep(i,n-1){
    if(check[i] != 0){
      increase.push_back(0 < check[i]);
    }
  }
  int ans = 1;
  // for(int i = 1; i < increase.size(); i++){
  // if(increase[i-1] != increase[i]){
  rep(i,(int)increase.size()-1){
    if(increase[i] != increase[i+1]){
      ans++;
      i++;
    }
  }
  cout << ans;
}


Measured memory_bytes: 1024
n = int(input())
a = [int(x) for x in input().split()]

min_abs = abs(a[0])  # a[0], ..., a[n-1]中の絶対値の最小値
sum = 0   # b[0] +  ... + b[n-1]
p_neg = 0  # a[0], ..., a[n-1]中の負の数の数が偶数なら0、奇数なら1
zero_exists = False  # a[0], ..., a[n-1]の中に0があるかどうか

for i in range(n):
    min_abs = min( min_abs, abs(a[i]))
    if a[i] < 0:
        p_neg = 1 - p_neg
        sum += -a[i]
    elif a[i] == 0:
        zero_exists = True
    else:
        sum += a[i]

if zero_exists or p_neg == 0:
    pass
else:
    sum -= 2 * min_abs

print(sum)


Measured memory_bytes: 14412
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	n := getInt()
	as := make([]int, n)
	for i := range as {
		as[i] = getInt()
	}

	ans := as[0]
	for _, a := range as {
		ans = gcd(ans, a)
	}

	fmt.Println(ans)
}

func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	if a%b == 0 {
		return b
	}
	return gcd(b, a%b)
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int k;
    cin >> k;
    vi a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << a[k-1] << endl;
}

Measured memory_bytes: 256
#include <iostream>
  #include <complex>
  #include <vector>
  #include <string>
  #include <algorithm>
  #include <cstdio>
  #include <numeric>
  #include <cstring>
  #include <ctime>
  #include <cstdlib>
  #include <set>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <list>
  #include <cmath>
  #include <bitset>
  #include <cassert>
  #include <queue>
  #include <stack>
  #include <deque>
 #include <iomanip>
 
  using namespace std;
   

//abcdefghijklmnopqrstuvwxyz
//ABCDEFGHIJKLMNOPQRSTUVWXYZ
  typedef long long ll;
  typedef long double lld;
//   typedef string str;
//   typedef unsigned long long ull;
  ll INF = INT_MAX;
  ll mod = 1000000007;
  // lld PI = 3.141592653;

// const int N = 2e5 + 5;

// int a[N];
// int n,k;
  


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

      ll n,k;
      cin>>n>>k;
      if (n>k){
        n%=k;
        n = min(n, k-n);
        cout<<n<<"\n";
      }else{
        cout<<min(n, k-n)<<"\n";
      }

      
}
  

Measured memory_bytes: 3168
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int solve()
{
	string s;cin>>s;
	ll n=sz(s);
	ll f=1;
	if((n&1)==1) f=0;
	for(ll i=0;i<n;i+=2)
	{
		string r = "";
		r+=s[i];
		if(i+1<n) r+=s[i+1];
		// whatis(r);
		if(r!="hi") f=0; 
	}
	if(f==1) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

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

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	// cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    string S; cin >> S;
    if (S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef	 long long int lli;
typedef long long ll;
typedef long double ld;
const int mod=1e9+7;
const int MAX=200005;
#define ALL(x) x.begin(),x.end()
#define all(x,k) x.begin(),x.begin()+k


void solve();

string getString(char x) 
{ 
    // string class has a constructor 
    // that allows us to specify size of 
    // string as first parameter and character 
    // to be filled in given size as second 
    // parameter. 
    string s(1, x); 
  
    return s;    
} 
bool sz(ll a, ll b)
{
	return a>b;
}
int main()
{


		
			solve();
		
		
	
	
	

return 0;
}

void solve()
{
	
int a,p;
cin>>a>>p;
cout<<(a*3+p)/2;
	
}



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

using namespace std;
vector<int> edge[100005];

int h1[100005],h2[100005];
int vis[100005];
void dfs1(int id,int deep)
{
    vis[id]=1;
    h1[id]=deep;
    int len=edge[id].size();
    for(int i=0;i<len;i++)
    {
        if(!vis[edge[id][i]])
            dfs1(edge[id][i],deep+1);
    }
}
void dfs2(int id,int deep)
{
    vis[id]=1;
    h2[id]=deep;
    int len=edge[id].size();
    for(int i=0;i<len;i++)
    {
        if(!vis[edge[id][i]])
            dfs2(edge[id][i],deep+1);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    memset(vis,0,sizeof(vis));
    dfs1(1,0);
    memset(vis,0,sizeof(vis));
    dfs2(n,0);
    int ans1=0,ans2=0;
    for(int i=2;i<=n-1;i++)
    {
        if(h1[i]<=h2[i])
            ans1++;
        else
            ans2++;
    }
    if(ans1>ans2)
        cout<<"Fennec"<<endl;
    else
        cout<<"Snuke"<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 11520
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
#define ll long long
#define pb push_back

int main() {
  int N,x;
  cin >> N;
  
  int ten = N / 10; // 10の位
  int hun = N /100; // 100の位

 
      if(ten - hun*10 <= hun ) {
          x = hun * 100 + hun * 10 + hun;
          if(x < N) {
            hun++;
             x = hun * 100 + hun * 10 + hun;
          }
      } else {
          hun++;
          x = hun * 100 + hun * 10 + hun;
      }

  

  cout << x << endl;

}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection) (collection).begin(), (collection).end()  // begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)       // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)      // repeat reverse
#define size(collection) ((ll) (collection).size())               // collection size

#endif


int main(void)
{
	ll n; cin >> n;
	vector<ll> b(n-1);

	rep(i, 0, n-1)
		cin >> b[i];

	vector<ll> a(n);
	a[0] = b[0];
	rep(i, 1, n-1)
		a[i] = min(b[i-1], b[i]);
	a[n - 1] = b[n - 2];



	cout << accumulate(all(a), 0LL);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  int a[n];
  for(int i =0;i<n;i++){
    cin >> a[i];
  }
 
  int b = (n-1)%(k-1)?1:0;
       
  cout << (n-1)/(k-1) +  b << endl;
}

Measured memory_bytes: 1016
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

    string s;
    cin >> s;

    ll ans = 0;

    auto dfs = [&](auto f, string sum, int now) {
        if (s.size() < now) {
            ll ret = 0;
            REP(i, sum.size()) {
                if (sum[i] == '+') {
                    ans += ret;
                    ret = 0;
                } else {
                    ret = ret * 10 + (sum[i] - '0');
                }
            }
            return;
        }
        string next = sum + "+" + s[now];
        f(f, next, now + 1);
        if (now != s.size()) {
            next = sum + s[now];
            f(f, next, now + 1);
        }
    };
    string start = to_string(s[0] - '0');
    dfs(dfs, start, 1);
    std::cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
X, Y, A, B, C = gets.split.map &:to_i
P = gets.split.map &:to_i
Q = gets.split.map &:to_i
R = gets.split.map &:to_i
P = P.max(X).sort
Q = Q.max(Y).sort
PQ = (P + Q).sort
R.sort!.reverse!
p PQ.zip(R).map{|a, b|
  [a, (b || 0)].max
}.inject:+

Measured memory_bytes: 39584
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int a, b, c; cin >> a >> b >> c;
	if(c > a + b){ cout << "NA" << endl; }
	else cout << max(0, c - a) << endl;
	return 0;
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(var) (var).begin(), (var).end()
#define sz(x) (int)x.size()
#define MAXX 9000000000000000000
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> > 
#define vvpi vector<vector<pair<int,int> > >

vi primes;
int isp[1000005],a[1000006],b[1000006];
map<int,int> maa;

void hcek()
{
	for(int i=2;i<=1000000;i++)
	{
		if(!isp[i])
		{
			primes.pb(i);
			for(int j= i * i ; j <=1000000;j+=i)
			{
				isp[j] = i;
			}
		}
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n,i,j,x,y;
	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	
	hcek();
	
	for(i=0;i<n;i++)
	{
		while(b[i] != 1)
		{
			if(!isp[b[i]])
			{
				if(maa[b[i]])
				{
					goto Ga;
				}
				maa[b[i]] = 1;
				b[i] = 1;
			}
			else
			{
				x = isp[b[i]];
				if(maa[x])
				{
					goto Ga;
				}
				while(b[i] % x == 0)
				{
					b[i] /= x;
					maa[x] = 1;
				}
			}
		}
	}

	cout << "pairwise coprime";
	return 0;
	
	Ga:
	{
		;
	}

	x = a[0];

	for(i=1;i<n;i++)
	{
		x = __gcd(x, a[i]);
	}

	if(x == 1)
	{
		cout << "setwise coprime";
	}
	else
	{
		cout << "not coprime";
	}

	return 0;
}

Measured memory_bytes: 27680
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main(){
    lint x;
    scanf("%lld", &x);
    printf("%lld\n", x/500*1000 + x%500/5*5);
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

int main(void) {
    string S, T;
    cin >> S >> T;

    int len = (int) S.size();

    for (int start = 0; start < len; start++) {
        bool ok = true;
        // printf("start: %d\n", start);
        for (int i = 0; i < len; i++) {
            int pos = (start + i) % len;
            // printf("%c, %c\n", S[i], T[pos]);
            if (S[i] != T[pos]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector< ii >
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }

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

vector<int> g[350];
vector<int> cst[350];
ii d[350][350];

int32_t main(){
  DESYNC;
  int n,m,l;
  cin >> n >> m >> l;
  for(int i=0; i<m; i++){
    int a,b,c;
    cin >> a >> b >> c;
    g[a].pb(b);
    g[b].pb(a);
    cst[a].pb(c);
    cst[b].pb(c);
  }

  //for each vertex do dijkstra
  for(int vertex=1; vertex<=n; vertex++){
    set< pair< ii, int> > s;
    for(int i=1; i<=n; i++) d[vertex][i] = ii(INF, -l);
    d[vertex][vertex] = ii(0, -l);
    s.insert(pair< ii, int>(ii(0, -l), vertex));
    while(s.size() > 0){
      int u = s.begin()->second;
      ii cur = s.begin()->first;
      s.erase(s.begin());
      if(d[vertex][u] != cur) continue;

      //break into cases
      for(int i=0; i<g[u].size(); i++){
        int v = g[u][i];
        int c = cst[u][i];

        //just consume fuel
        if(c <= abs(cur.ss) and d[vertex][v] > ii(cur.ff, cur.ss + c)){
          d[vertex][v] = ii(cur.ff, cur.ss + c);
          s.insert(pair< ii, int>(d[vertex][v], v));
        }

        //put fuel and go
        if(c <= l and d[vertex][v] > ii(cur.ff +1, -l + c)){
          d[vertex][v] = ii(cur.ff +1, -l + c);
          s.insert(pair< ii, int>(d[vertex][v], v));
        }
      }
    }
  }
  int q;
  cin >> q;
  while(q--){
    int s,t;
    cin >> s >> t;
    if(d[s][t].ff == INF) cout << -1 << endl;
    else cout << d[s][t].ff << endl;
  }
}




Measured memory_bytes: 4608
line = raw_input().split(" ")
w = int(line[0])
a = int(line[1])
b = int(line[2])

aw = a + w
bw = b + w
if bw < a:
    print a - bw
elif bw >= a and bw <= aw:
    print 0
elif bw > aw:
    if b > aw:
        print b - aw
    else:
        print 0


Measured memory_bytes: 2568
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String[] tokens = in.nextLine().split(" ");
		int a = Integer.parseInt(tokens[0]);
		int b = Integer.parseInt(tokens[1]);
		int c = Integer.parseInt(tokens[2]);
		int x = Integer.parseInt(tokens[3]);
		int y = Integer.parseInt(tokens[4]);

		if ((a + b) <= (2 * c)) {
			int result = a * x + b * y;
			System.out.println(result);
		} else {
			int r = 2 * c * Math.max(x, y);
			if (x <= y) {
				int cNum = 2 * x;
				int bNum = y - x;
				int result = Math.min(cNum * c + bNum * b, r);
				System.out.println(result);
			} else {
				int cNum = 2 * y;
				int aNum = x - y;
				int result = Math.min(cNum * c + aNum * a, r);
				System.out.println(result);
			}
		}
		in.close();
	}

}


Measured memory_bytes: 23124
count = int(input())
s = list(map(int,input().split()))
total = 0
if count > 2:
    for i in range(count-2):
        a = s[i]
        for j in range(i+1,count-1):
            b = s[j]
            for k in range(j+1,count):
                c = s[k]
                if a+b > c and a+c > b and b+c > a and a != b and b != c and a != c:
                    total += 1
print(total)

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

int main() {
 int N,M,C;
  cin >> N >> M >> C;
  vector<int> B(M);
  vector<int> A(N * M);
  vector<int> ans(1);
  ans.at(0) = C;
  int count = 0;
  int sum = 0;
  for(int i = 0; i < M; i++ ) {
    cin >> B.at(i);
  }
  for( int i = 0;i < N * M; i++) {
    cin >> A.at(i);
  }
  for( int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      ans.push_back(A.at(i*M + j) * B.at(j));
    }
    for( int j = 0; j < M + 1; j++) {
      sum += ans.at(j);
    }
    if(sum > 0) {
      count++;
    }
    sum = 0;
    for( int j = 0; j < M; j++) {
      ans.pop_back();
    }
  }
  cout << count << endl;
}
    

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

struct edge{int to, cap, rev;};
vector<edge> G[101];
bool used[101];
int dfs(int v, int t, int f){
	if(v == t)return f;
	used[v] = true;
	for(int i = 0;i < G[v].size();i++){
		edge &e = G[v][i];
		if(!used[e.to] && e.cap > 0){
			int d = dfs(e.to, t, min(f, e.cap));
			if(d > 0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int main(){
	int n, m, v, u, c;
	scanf("%d%d", &n, &m);
	for(int i = 0;i < m;i++){
		scanf("%d%d%d", &v, &u, &c);
		int t = G[u].size();
		G[v].push_back((edge){u, c, G[u].size()});
		t = G[v].size()-1;
		G[u].push_back((edge){v, 0, G[v].size()-1});
	}
	
	int flow = 0;
	while(1){
		fill(used, used+101, 0);
		int f = dfs(0, n-1, inf);
		if(f == 0)break;
		flow += f;
	}
	
	printf("%d\n", flow);
	return 0;
}


Measured memory_bytes: 3332
#include "bits/stdc++.h"
#define MY_ABS(N) ((N>0)?N:(-1*N))
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> H(N);
    for (long long 
    &v : H){
        cin >> v;
    }

    long long maxH = 1;
    bool flgSub = true;
    for (int i = 0; i < N; i++){
        // cout << maxH << ' ' << H[i] << endl;
        if((maxH - H[i]) > 1){
            flgSub = false;
            break;
        }

        if(maxH < H[i]) {
            maxH = H[i];
        }
    }

    if(!flgSub) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 1024
<?php
  
   $w=trim(fgets(STDIN));
$m=100000;


for($i=1;$i<=$w;$i++){
$m *= 1.05;
if($m%1000==0){
$m=floor( $m/1000 )*1000;
}else{
$m=floor( $m/1000 )*1000 +1000;
}
}
echo $m . "\n";;




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

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

class Space {
public:
	int X, Y, Z;
	const int dx[13] = { 0,1,1,1,0,0,-1,-1,-1,1,1,1,0 };
	const int dy[13] = { 1,1,1,1,1,1,1,1,1,0,0,0,0 };
	const int dz[13] = { 0,-1,0,1,-1,1,-1,0,1,-1,0,1,1 };
	vector<vector<vector<int>>> P;
	vector<vector<int>> S;
	Space(int X, int Y, int Z) :X(X), Y(Y), Z(Z) {
		P = vector<vector<vector<int>>>(X, vector<vector<int>>(Y, vector<int>(Z, -1)));
		S = vector<vector<int>>(X, vector<int>(Y, 0));
	}
	bool inrange(int x, int y, int z) {
		return 0 <= x&&x < X && 0 <= y && y < Y && 0 <= z && z < Z;
	}
	int count(int x, int y, int z, int d, int t, int r) {
		if (P[x][y][z] != t)return 0;
		int nx = x + dx[d] * r, ny = y + dy[d] * r, nz = z + dz[d] * r;
		return inrange(nx, ny, nz) ? count(nx, ny, nz, d, t, r) + 1 : 1;
	}
	void update(int x, int y, int value) {
		P[x][y][S[x][y]++] = value;
	}
	int query(int x, int y, int turn, int M) {
		update(x, y, turn);
		int ret = 0;
		for (int d = 0; d < 13; d++) {
			int cnt = 0;
			cnt += count(x, y, S[x][y] - 1, d, turn, 1);
			cnt += count(x, y, S[x][y] - 1, d, turn, -1);
			cnt--;
			if (cnt >= M)
				return turn;
		}
		return -1;
	}
};



signed main() {
	for (int N, M, P; cin >> N >> M >> P&&N;) {
		Space S(N, N, N);
		vector<int> x(P), y(P);
		rep(i, 0, P) {
			cin >> x[i] >> y[i];
			x[i]--, y[i]--;
		}
		bool draw = true;
		rep(i, 0, P) {
			int res = S.query(x[i], y[i], i & 1, M);
			if (res == 1) {
				cout << "White " << i + 1 << endl;
				draw = false;;
				break;
			}
			else if (res == 0) {
				cout << "Black " << i + 1 << endl;
				draw = false;
				break;
			}
		}
		if (draw)cout << "Draw" << endl;
	}
}

Measured memory_bytes: 2996
#include<stdio.h>

int main(){
  int x,y,r;
  
  scanf("%d%d",&x,&y);
  if(x<y){
    r=x;
    x=y;
    y=r;
      }

  
    while(y>0){
      r=x%y;
      x=y;
      y=r;
  }
    printf("%d\n",x);
  return 0;
}



Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9 + 7;
 
int dx[]={-1, 0, 1, 0};
int dy[]={0, -1, 0, 1};
 
 

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


 
 int n;
 cin>>n;
 string s;
 cin>>s;
 int ans=0;
 for(int i=0;i<n-2;i++)
 {
    if(s.substr(i,3)=="ABC")ans++;
 }
 cout<<ans<<"\n";
 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll N = 5050;
ll bit[5050];
void add(ll a, ll w) {
	a++;
	for (ll x = a; x <= N; x += x & -x) bit[x] += w;
}
ll sum(ll a) {
	a++;
	ll ret = 0;
	for (ll x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n - 1);
	REP(i, n - 1) cin >> a[i];
	vector<vector<ll>> b(n, vector<ll>(m));
	REP(i, n) REP(j, m) cin >> b[i][j];
	vector<stack<pair<ll, P>>> seg(m);
	ll ans = 0;
	REP(i, n) {
		REP(j, m) {
			while(!seg[j].empty() && seg[j].top().first <= b[i][j]) {
				ll num = seg[j].top().first;
				P p = seg[j].top().second;
				add(p.first, -num);
				add(p.second, num);
				seg[j].pop();
			}
			ll l = 0;
			if(!seg[j].empty()) l = seg[j].top().second.second;
			add(l, b[i][j]);
			add(i + 1, - b[i][j]);
			seg[j].push(make_pair(b[i][j], P(l, i + 1)));
		}
		ll dist = 0;
		for(ll j = i; j >= 0; j--) {
			ans = max(ans, sum(j) - dist);
			if(j) dist += a[j - 1];
		}
	}
	cout << ans << endl;
	return 0;
}

/* --------------------------------------- */


Measured memory_bytes: 8576
#include <iostream>
#include <math.h>

using namespace std;

int main (void){
	int A,B,x1,x2,x3,m1,m2;
	cin >> A >> B;
	x1 = A + B;
	x2 = A - B;	
	x3 = A * B;
	m1 = (x1+x2+abs(x1-x2))/2;
	m2 = (x3+m1+abs(x3-m1))/2;
	cout << m2;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    int N, M, sbuf, cbuf;
    vector<pair<int, int>>sc;
    vector<int> power10 = {1, 10, 100};
    cin >> N >> M;
    vector<int> scfinal(N, -1);
    for(int i=0; i<M; i++){
        cin >> sbuf >> cbuf;
        sbuf--;
        sc.push_back(pair<int, int>(sbuf, cbuf));
    }
    sort(sc.begin(), sc.end());
    bool exists = true;
    for(int i=0; i<M; i++){
        if(scfinal[sc[i].first] == -1){
            scfinal[sc[i].first] = sc[i].second;
        }else if(scfinal[sc[i].first] != sc[i].second){
            exists = false;
            break;
        }
    }
    if((N != 1)&&(scfinal[0] == 0))exists = false;
    int res = -1;
    if(exists){
        res++;
        for(int i=0; i<N; i++){
            if(i > 0){
                res += (scfinal[i] < 0 ? 0 : scfinal[i])*power10[N-i-1];
            }else{
                res += (scfinal[i] < 0 ? 1 : scfinal[i])*power10[N-i-1];
            }
        }
        if((res == 0)||(M == 0)){
            res = (N == 1 ? 0 : power10[N-1]);
        }
    }
    cout << res << endl;
    return 0;
}

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

int main(){
	int x[3000], y[3000];
	for (int i = 0; i < 3000; i++){
		cin >> x[i] >> y[i];
		if (x[i] == 0 && y[i] == 0){
			break;
		}
	}
	for (int i = 0; i < 3000; i++){
		if (x[i] == 0 && y[i] == 0){
			break;
		}
		if (x[i] <= y[i]){
			cout << x[i] <<" "<< y[i] << endl;
		}
		else{
			cout << y[i] <<" "<< x[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3088
N = int(input())
A = list(map(int, input().split()))
money = 1000
stock = 0
for i in range(N-1):
    if A[i+1] > A[i]:
        stock = money // A[i]
        money = money % A[i]
        money += stock * A[i+1]
print(money)


Measured memory_bytes: 9056