akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);




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

	int N;
	cin >> N;
	vector<int>A(100001, 0);
	rep(i, N) {
		int p;
		cin >> p;
		A[p]++;
	}
	int c1 = 0, c2 = 0;
	rep(i, 100001) {
		if (3 <= A[i])A[i] = 2 - (A[i] % 2);
		if (A[i] == 1)c1++;
		if (A[i] == 2)c2++;
	}
	c1 += c2;
	c2 %= 2;
	c1 -= c2;
	cout << c1 << endl;




	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
//Author: Ezio Sam
/* Shorthands */
#define ll long long
#define pb push_back
#define em emplace_back
#define mp make_pair
#define sp " "
#define cs "Case "
#define fi first
#define sn second

/* STL */
#define mem(a,n) memset(a, n, sizeof(a));
#define all(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define sz(x)  (int)x.size()
#define mx(v)  *max_element(v.begin(),v.end())
#define mxi(v) distance(v.begin(),max_element(v.begin(),v.end()))
#define mxa(a) *max_element(a, a.size())
#define r(a)   reverse(a.begin(),a.end())
/* loops */
#define fr(i,n)   for(__typeof(n) i=0;i<(n);i++)
#define fn(i,n)   for(__typeof(n) i=1;i<=(n);i++)
/*Special*/
#define Ezio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(something)  cerr<<#something<<" - "<<something<<"\n";

int main()
{

   Ezio
   ll t,m,n,x,a,b;
   string s;

   cin>>n>>x;

   vector<string> v(n);
   fr(i,n)cin>>v[i];
   sort(all(v));

   for(auto i:v)cout<<i;
   cout<<endl;
   return 0;
}


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

int main(){
  int n,ans=1,tmp,ans_cnt=0;
  cin >> n;



  for(int i = 1; i <= n; i++){
    tmp = i;
    int cnt = 0;
    while(tmp%2 == 0){
      cnt++;
      tmp /= 2;
    }

    if(cnt>ans_cnt){
      ans = i;
      ans_cnt = cnt;
    }
    //cout << ans << endl;
  }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <queue>
#include <stack>
using namespace std;
 
typedef pair<long long int,long long int>pa;
#define resize(A) A.resize(unique(A.begin(), A.end()) - A.begin())
#define pb push_back
 
# define  MAX 200005
long long int MOD=998244353;
long long int INF=1e18;
 
int main()
{
    
       ios_base::sync_with_stdio(false); 
       cin.tie(NULL);
     cout.tie(NULL);
      long long int i,j,k=0,l=0,r=0,m=0,n,p=0,cnt=0,cnt1=0,x,y,z=0,a,b,low,mid,high,ans=0,maxi=0,mini=INF,t;
cin>>a>>b;
if((a+b)%2==0)
cout<<(a+b)/2;
else
cout<<"IMPOSSIBLE";

}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static final int MOD = 2019;
    public Main(){
        Scanner SC = new Scanner(System.in);

        String S = SC.next();
        int L = S.length();
        int[] N = new int[L];
        for(int i=0;i<L;i++){
            N[i] = S.charAt(i) - '0';
        }

        Map<Integer, Integer> MAP = new HashMap<Integer, Integer>();
        int key = 0;
        int modexp10 = 1;
        for(int i=0;i<L;i++){
            key = (key + N[L-i-1] * modexp10) % MOD;
            modexp10 = modexp10 * 10 % MOD;
            int v = MAP.getOrDefault(key, 0);
            MAP.put(key, v+1);
        }

        int total = MAP.getOrDefault(0, 0);
        for(Integer i : MAP.keySet()){
            int t = MAP.get(i);
            total += t * (t - 1) / 2;
        }

        System.out.println(total);
    }

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


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

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

  set<int> color;
  int high = 0;

  for(int i=0;i<n;i++){
    int rate;
    cin >> rate;
    if(rate>=3200) high++;
    else color.insert(rate/400);
  }
  const int ans_min = max(1,int(color.size()));
	const int ans_max = high + int(color.size());
  cout << ans_min << " " << ans_max << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
d = dict()
for i in range(n):
    s = list(input())
    if s[0] == "M" or s[0] == "A" or s[0] == "R" or s[0] == "C" or s[0] == "H":
        if s[0] not in d:
            d[s[0]] = 1
        else:
            d[s[0]] += 1
count = 0
d = list(d.values())
if len(d) == 3:
    count += d[0] * d[1] * d[2]
elif len(d) == 4:
    count += d[0] * d[1] * d[2]
    count += d[3] * d[1] * d[2]
    count += d[0] * d[1] * d[3]
    count += d[0] * d[3] * d[2]
elif len(d) == 5:    
    count += d[0] * d[1] * d[2]
    count += d[3] * d[1] * d[2]
    count += d[0] * d[1] * d[3]
    count += d[0] * d[3] * d[2]

    # count += d[0] * d[1] * d[2]
    count += d[4] * d[1] * d[2]
    count += d[0] * d[1] * d[4]
    count += d[0] * d[4] * d[2]

    # count += d[4] * d[1] * d[2]
    # count += d[3] * d[1] * d[2]
    count += d[4] * d[1] * d[3]
    count += d[4] * d[3] * d[2]

    # count += d[0] * d[4] * d[2]
    # count += d[3] * d[4] * d[2]
    count += d[0] * d[4] * d[3]
    # count += d[0] * d[3] * d[2]


print(count)

Measured memory_bytes: 9260
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <numeric>
#include <string>

using namespace std;

void search__(int point, vector<double> &dist, int counter, vector<double> &distlist, vector<int> const &x, vector<int> const &y)
{
    int n = dist.size();
    double maxdist = (double)0;

    if (counter == n)
    {
        for (int i = 0; i < n; i++)
        {
            maxdist = max(maxdist, dist[i]);
        }
        distlist.push_back(maxdist);
    }

    for (int j = 0; j < n; j++)
    {
        vector<double> distcpy = dist;

        if (dist[j] != -1)
            continue;
        double d = sqrt((x[point] - x[j]) * (x[point] - x[j]) + (y[point] - y[j]) * (y[point] - y[j]));
        distcpy[j] = dist[point] + d;
        search__(j, distcpy, counter + 1, distlist, x, y);
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
    }

    int counter = 1;
    vector<double> distlist;
    for (int i = 0; i < n; i++)
    {
        vector<double> dist(n, -1);
        dist[i] = (double)0;
        search__(i, dist, counter, distlist, x, y);
    }

    counter = 0;
    double sum = 0;
    for (auto &&d : distlist)
    {
        sum += d;
        counter++;
    }

    double ans = sum / (double)counter;

    printf("%lf", ans);

    return 0;
}

Measured memory_bytes: 892
#define _USE_MATH_DEFINES  // M_PI等のフラグ

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>

#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

string replace_with_str(string str, string str_from, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(str_from, pos), pos != string::npos) {
        str.replace(pos, str_from.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main(int argc, char const *argv[]){
    int N;
    cin >> N;
    int max_p = 0;
    int ans = 0;
    for(int i=0; i<N; i++){
        int p;
        cin >> p;
        ans += p;
        max_p = max(max_p, p);
    }

    ans = ans - max_p + int(max_p/2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef map<int, int> mi;
typedef set<int> si;
#define VV(T) vector<vector< T > >
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define invrep(i, n) for(int i = (n)-1; i >= 0; i--)        // n-1, n-2, ..., 0
#define invREP(i, x, n) for(int i = (n)-1; i >= (x; i--)    // n-1, n-2, ..., x
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define PB push_back

#define COUT(x) cout << (x) << endl
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl

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


int main(){
    int s; cin >> s;
    int loop = 1;
    while(s != 4 && s != 2 && s!= 1){
        s = (s % 2 == 0) ? s / 2 : s * 3 + 1;
        loop++;
    }
    COUT(loop + 3);
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int r, g, b;
	cin >> r >> g >> b ;
	int tmp;
	tmp = (100*r+10*g+b)%4;
	if(tmp==0){
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}


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

const int maxn = 110;

int h,w;
int a[maxn][maxn];
vector<int> g[maxn * maxn];
int cnt = 0, id[maxn][maxn];
int level[maxn * maxn], pre[maxn * maxn];
queue<int> que;
int s,t;
pair<int,int> cors,cort;
bool vis[maxn * maxn];

void link(int u,int v)
{
	g[u].push_back(v);
}

bool check(int i, int j)
{
	if (a[i][j] == 'S' || a[i][j] == 'T' || a[i][j] == 'o') return true;
	return false;
}

void build()
{
	for (int i=1;i<=h;i++) 
		for (int j=1;j<=w;j++) id[i][j] = ++cnt;
	for (int i=1;i<=h;i++)
	{
		for (int j=1;j<=w;j++)
		{
			if (a[i][j] == 'S') s = id[i][j], cors = make_pair(i,j);
			if (a[i][j] == 'T') t= id[i][j], cort = make_pair(i,j);
			if (!check(i,j) || a[i][j] == 'T') continue;
			for (int k=1;k<=w;k++)
			{
				if (j==k) continue;
				if (check(i,k)) link(id[i][j], id[i][k]);
			}
			for (int k=1;k<=h;k++)
			{
				if (i == k) continue;
				if (check(k,j)) link(id[i][j], id[k][j]);
			}
		}
	}
}

bool bfs()
{
	memset(level,-1,sizeof(level));
	level[s] = pre[s] = 0;
	
	que.push(s);
	while (!que.empty())
	{
		int u = que.front(); que.pop();
		for (int i=0;i<(int)g[u].size();i++)
		{
			int v = g[u][i];
			if (level[v] == -1 && !vis[v])
			{
				level[v] = level[u] + 1;
				pre[v] = u;
				que.push(v);
			}
		}
	}
	if (level[t] == -1) return false;
	int tt = t;
	while (tt)
	{
		//cout<<tt<<endl;
		vis[tt] = true;
		tt = pre[tt];
	}
	vis[t] = vis[s] = false;
	return true;
}

int main()
{
	//freopen("F.in","r",stdin);
	scanf("%d%d",&h,&w);
	for (int i=1;i<=h;i++)
	{
		char str[110];
		scanf("%s",str);
		for (int j=1;j<=w;j++) a[i][j] = str[j-1];
	}
	build();
	int ans = 0;
	if (cors.first == cort.first || cors.second == cort.second)
	{
		puts("-1");
		return 0;
	}
	while (bfs())
	{
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 10880
import java.util.*;
import java.io.*;

public class Main{
	public static int solve(int[] n){
		if( n.length == 1 ){
			return n[0]%10;
		}
		int[] temp = new int[n.length-1];
		for(int i = 0; i < temp.length; i++){
			temp[i] = n[i]+n[i+1];
		}
		return solve(temp);
	}
	
	public static void main(String[] args) throws IOException{
		Scanner stdIn = null;
		List<Integer> result = new ArrayList<Integer>();
		
		try{
			stdIn = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
			while( stdIn.hasNext() ){
				long x = stdIn.nextLong();
				int[] n = new int[10];
				for(int i = 9; i >= 0; i--){
					n[i] = (int)(x%10);
					x /= 10;
				}
				result.add(solve(n));
			}
			for(Integer ans : result){
				System.out.println(ans);
			}
		} finally {
			if( stdIn != null ){
				stdIn.close();
			}
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


int main()
{
	int n,a,b;
	cin>>n>>a>>b;
	cout<<min(a,b)<<" "<<max(0,a+b-n)<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <cassert>
using namespace std;

struct Node {
  Node* left;
  Node* right;
  Node(Node* l, Node* r): left(l), right(r) {}
};

Node dummy(NULL, NULL);

pair<int, Node*> parse(const string& str, int k)
{
  pair<int, Node*> r1, r2;
  assert(str[k] == '(');
  if (str[k + 1] == '(') {
    r1 = parse(str, k + 1);
  } else {
    r1 = make_pair(k + 1, (Node*)NULL);
  }
  assert(str[r1.first] == ',');
  if (str[r1.first + 1] == '(') {
    r2 = parse(str, r1.first + 1);
  } else {
    r2 = make_pair(r1.first + 1, (Node*)NULL);
  }
  assert(str[r2.first] == ')');
  return make_pair(r2.first + 1, new Node(r1.second, r2.second));
}

Node* intersection_or_union(char op, Node* node1, Node* node2)
{
  if (!node1) { node1 = &dummy; }
  if (!node2) { node2 = &dummy; }
  bool b1 = (op == 'i') ? (node1->left && node2->left) : (node1->left || node2->left);
  bool b2 = (op == 'i') ? (node1->right && node2->right) : (node1->right || node2->right);
  Node* left = b1 ? intersection_or_union(op, node1->left, node2->left) : NULL;
  Node* right = b2 ? intersection_or_union(op, node1->right, node2->right) : NULL;
  return new Node(left, right);
}

void print_tree(Node* node)
{
  cout << "(";
  if (node->left) {
    print_tree(node->left);
  }
  cout << ",";
  if (node->right) {
    print_tree(node->right);
  }
  cout << ")";
}

int main()
{
  char op;
  string str1, str2;
  while (cin >> op >> str1 >> str2) {
    Node* tree1 = parse(str1, 0).second;
    Node* tree2 = parse(str2, 0).second;
    print_tree(intersection_or_union(op, tree1, tree2));
    cout << endl;
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>


using namespace std;
using namespace __gnu_pbds;
#define MOD  1000000007
#define ll long long
#define int long long
#define INF 1e18
#define ar array
#define MAX 1000004
#define wt(x) int x;cin>>x;while(x--)

typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> pbds;

void  c_p_c(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
#ifndef ONLINE_JUDGE
  freopen("input1.txt","r",stdin);
  freopen("output1.txt","w",stdout);
#endif
 
}
ll power(ll a,ll b,int mod){
    a=a%mod;
    if(a==0){
        return 1;
    }
    ll res=1;
    while(b){
        if(b&1){
            res=(res*a)%mod;
        }
        b>>=1;
        a=(a*a)%mod;
    }
    return res;
 }
 
  

 int32_t main() {

c_p_c();
ll n;
    cin>>n;
    int ans = 0;
    for(ll m = 2; m*m <= n; m++){
        if(n%m)continue;
        int cnt = 0;
        while(n%m == 0){
            n /= m;
            cnt++;
        }
        int mx = 1;
        for(int i = 1; i <= 50; i++){
            if(i*(i + 1)/2 <= cnt)mx = i;
        }
        
        ans += mx;
    }
    if(n > 1)ans++;
    cout<<ans<<endl;
    

return 0;

}
 


   

        



Measured memory_bytes: 3676
A,B,C,X,Y = map(int, input().split())
ans = 5000 * 10**5 * 4 + 1
for c in range(0,max(X,Y)*2+1,2):
    a = c * C
    x,y = max(0,X-c//2), max(0,Y-c//2)
    a += A*x + B*y
    ans = min(ans, a)

print(ans)

Measured memory_bytes: 39408
#include <bits/stdc++.h>
#include<math.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int main() {
  

  int INF=10000000;
  
  
  
  bool ans=true;
  vector<vector<int>> c(3, vector<int>(3));
  for(int i=0; i<3;i++){
    for(int j=0; j<3;j++){
      cin>>c[i][j];
    }
  }
 
    
    for(int i=1; i<3;i++){
      if(c.at(i).at(0)-c.at(i).at(1)!=c.at(0).at(0)-c.at(0).at(1)||c.at(i).at(0)-c.at(i).at(2)!=c.at(0).at(0)-c.at(0).at(2)){
        ans=false;
      }
    }

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






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

struct edge{
    ll to;
    ll cost;
};

vector<edge> v[100001];
ll x[100001];

bool hoge(ll z){
    ll vs=v[z].size();
    rep(i,0,vs-1){
        if(x[v[z][i].to]==-inf){
            x[v[z][i].to]=x[z]+v[z][i].cost;
            if(!hoge(v[z][i].to)){
                return false;
            }
        }else{
            if(x[v[z][i].to]!=x[z]+v[z][i].cost){
                return false;
            }
        }
    }
    return true;
}



int main(){fastio
    ll n,m;cin>>n>>m;
    ll l,r,d;
    edge e;
    rep(i,0,m-1){
        cin>>l>>r>>d;
        e.cost=d;
        e.to=r;
        v[l].pb(e);
        e.cost=-d;
        e.to=l;
        v[r].pb(e);
    }
    rep(i,1,n){
        x[i]=-inf;
    }
    rep(i,1,n){
        if(x[i]==-inf){
            x[i]=0;
            if(!hoge(i)){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 16512
import sys
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(-i)
            #if i != n // i:
            #    divisors.append(n//i)
            #    divisors.append(-n//i)
    # divisors.sort()
    return divisors

def f(p,T):
    q=T//p
    #print(p,q)
    m=int(math.sqrt(T))+1
    for j in range(-m-1,m+1):
        i = j+ p
        k=i**2*(i*(i+j) + (j**2)) + (j**3)*(i+j)
        if (k==q):
            print(i,j)
            return True
    else:
        return False
T=int(input())
ya=make_divisors(T)
for p in ya:
    if f(p,T):
        break

Measured memory_bytes: 65180
/// a.cpp

# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < __typeof(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < ll >
# define pb push_back
# define pdd pair < db , db >
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    static int s[1 << 20];
    int n;
    fi>>n;
    for (int i = 1;i <= n;++i)
        fi>>s[i];
    static int dp[1 << 20];
    static int nxt1[1 << 20];
    static int nxt2[1 << 20];
    for (int i = 1;i <= n;)
    {
        int j = i;
        while (j < n && s[j] <= s[j + 1])
            ++j;
        for (int k = i;k <= j;++k)
            nxt1[k] = i - 1;
        i = j + 1;
    }
    for (int i = 1;i <= n;)
    {
        int j = i;
        while (j < n && s[j] >= s[j + 1])
            ++j;
        for (int k = i;k <= j;++k)
            nxt2[k] = i - 1;
        i = j + 1;
    }
    for (int i = 1;i <= n;++i)
        dp[i] = 1 + min(dp[nxt1[i]],dp[nxt2[i]]);
    fo << dp[n] << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}


Measured memory_bytes: 6784
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2


def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n, d = [int(x) for x in input().split()]
    c = 0
    for i in range(n):
        x, y = [int(x) for x in input().split()]
        if x**2 + y**2 <= d**2:
            c += 1
    print(c)


#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()


Measured memory_bytes: 77696
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(long long i=0; i<(int)n; i++)
#define rep1(i,n) for(long long i=1; i<(int)n; i++)
#define repa(i,a,n) for(long long i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
const int mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a / gcd(a, b)*b;}

int N, M, K, H, W, L, R, X;
//string S, T;
signed main(){
  cin >> N;
  int T; cin >> T;
  rep(i,N-1){
    int a; cin >> a;
    T = lcm(T,a);
  }
  cout << T << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>
 
// #include <unordered_set>
// #include <unordered_map>
 
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
 
#define pb push_back
#define mp make_pair
 
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
 
typedef std::pair<int,int> P;
typedef long long ll;
typedef long double ld;
 
const int MOD = 1000000007;
const int INF = 1e9;
const ll LINF = INF * 1ll * INF;
const ld DINF = 1e200;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
using namespace std;
 
#define int long long

signed main(){
	

	int h,w,d;
	cin>>h>>w>>d;

	int seki=h*w;

	int ans=0;
	vector<int> ansv;

	int grid[h][w]={0};
	int vx[seki];
	int vy[seki];
	int imos[seki]={0};

	REP(i,h){
		REP(j,w){
			cin>>grid[i][j];
			vx[grid[i][j]]=i;
			vy[grid[i][j]]=j;
		}
	}

	// sort(v.begin(),v.end());

	for(int i=d+1;i<=h*w;i++){
		imos[i]=imos[i-d]+(abs(vx[i]-vx[i-d])+abs(vy[i]-vy[i-d]));
	}



	// REP(i,seki){
	// 	cout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<endl;
	// }


	int q;
	int l,r;
	int tmp_l,tmp_r;



	cin>>q;

	int tmp_ans;
	REP(i,q){
		cin>>l>>r;
		tmp_ans=imos[r]-imos[l];

		cout<<tmp_ans<<endl;
	}
	
		// tmp_l=v[l-1].second.first;
		// tmp_r=v[l-1].second.second;
		// cout<<tmp_l<<" "<<tmp_r<<endl;

	// 	for(int j=l;j<r;j+=d){

	// 		// cout<<v[(j-1)+d].second.first<<" "<<v[j-1].second.first<<" "<<v[(j-1)+d].second.second<<" "<<v[j-1].second.second<<endl;

	// 		ans+=abs(v[(j-1)+d].second.first-v[j-1].second.first)+abs(v[(j-1)+d].second.second-v[j-1].second.second);
	// 	}

	// 	ansv.pb(ans);
	// }

	// REP(i,q){
	// 	cout<<ansv[i]<<endl;
	// }


	


}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
using namespace std;
/*ll power(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=y/2;
    }
    return res;
}*/
int main()
{

ll n,m,i,j,k,c=0,ans=0;
cin>>n>>m;
char ch,arr2[n+1][m+1];
ll arr[n+1][m+1]={0},arr1[n+1][m+1]={0};
vector<ll>v,v1;
for(i=1;i<=n;i++)
{
    c=0;
        for(j=1;j<=m;j++)
        {
            cin>>ch;
            arr2[i][j]=ch;
            if(ch=='.')
            {

                c++;
            }
            else if(ch=='#')
            {
                v.pb(c);
                c=0;
                arr[i][j]=-1;
                continue;
            }
            if(j==m)
                v.pb(c);
        }
}
for(j=1;j<=m;j++)
{
    c=0;
    for(i=1;i<=n;i++)
    {
        ch=arr2[i][j];

        if(ch=='.')
            {

                c++;
            }
            else if(ch=='#')
            {
                v1.pb(c);
                c=0;
                arr1[i][j]=-1;
                continue;
            }
            if(i==n)
                v1.pb(c);
    }
 }
k=0;
for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
    {
        if(arr[i][j]==-1)
        {
            k++;
            continue;
        }
        arr[i][j]=v[k];
        if(j==m)
        {
            k++;
            continue;
        }
    }
}
k=0;
for(j=1;j<=m;j++)
{
    for(i=1;i<=n;i++)
    {
        if(arr1[i][j]==-1)
        {
            k++;
            continue;
        }
        arr1[i][j]=v1[k]+arr[i][j]-1;
            ans=max(ans,arr1[i][j]);
            if(i==n)
            {
                k++;
                continue;
            }
    }
}
cout<<ans<<endl;
}



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

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  int D = A;
  string output = "NO";
  for(int i=0;i<B;i++){
    A %= B;
    if(A == C){
      output = "YES";
      break;
    }
    A += D;
  }
  cout <<  output << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;//998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template<class _T> static void getint(_T& a) {
	if (sizeof(_T) > sizeof(int)) {
		scanf("%lld", &a);
	}
	else {
		scanf("%d", &a);
	}
}
template <class _T> static _T tp_abs(_T a) {
	if (a < (_T)0) {
		a *= (_T)-1;
	}
	return a;
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	int N;
	get(N);

	std::vector<std::vector<int>> open(N, std::vector<int>(10, 0)), prof(N, std::vector<int>(11, 0));

	for (int i = 0; i < N; i++) {
		for (int t = 0; t < 10; t++) {
			get(open[i][t]);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int t = 0; t <= 10; t++) {
			get(prof[i][t]);
		}
	}

	int ans = -MOD_NUM;
	for (int bit = 1; bit < (1 << 10); bit++) {
		std::vector<int> match(N, 0);
		for (int day = 0; day < 10; day++) {
			if (bit & (1 << day)) {
				for (int i = 0; i < N; i++) {
					if (open[i][day]) {
						match[i]++;
					}
				}
			}
		}
		int pr = 0;
		for (int i = 0; i < N; i++) {
			pr += prof[i][match[i]];
		}
		ans = std::max(ans, pr);
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 3720
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

template<typename V>
constexpr string join(const V &v, const string &sep) {
  stringstream ss;
  if (v.size()) ss << v[0];
  loop(i, 1, v.size()) ss << sep << v[i];
  return ss.str();
}

void solve() {
  int n;
  while (cin >> n, n) {
    string s;
    getline(cin, s);
    vs v;
    map<string, int> m;
    while (n--) {
      getline(cin, s);
      istringstream ss(s);
      while (ss >> s) v.pb(s), m[s]++;
    }
    char k;
    cin >> k;
    set<string> t;
    for (auto &x : v) {
      if (x.front() == k) t.insert(x);
    }
    vs w;
    copy(all(t), back_inserter(w));
    stable_sort(all(w), [&](string a, string b) {
      return m[a] > m[b];
    });
    if (w.size() > 5) w.resize(5);
    if (w.size() == 0) w.pb("NA");
    cout << join(w, " ") << endl;
  }
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_bit(n) for (int bit = 0; bit < (1<<n); ++bit)
#define all(x) (x).begin(),(x).end()
#define ll long long
#define ld long double
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define SP <<" "<<
#define CST(x) cout<<fixed<<setprecision(x)
using namespace std;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> Graph;

//条件式 ? 真の場合の文 : 偽の場合の文
//abs(x) = (x の絶対値)
//string S  S,at(i),S += T,S += c,S.size(),S.substr(l)l文字目から最後まで,
///S.substr(l, r)l文字目からl+r-1文字目 n文字目から0個で空列を返せる
//*min_element(all(x)) *max_element(all(x))
//vi x; x.back(),x.front(),x.push_back(),x.pop_back()
//swap(a, b)
//gcd(a, b)最大公約数
//sort(all(x)),reverse(all(x)),sort(x.begin()+l,a.begin()+r)lからrまで
//stack<int> a; a.push(x),a.pop(),a.top(),a.empty()bool
//queue<int> b; b.push(x),b.pop(),b.front(),b.empty()bool,b.size() 要素が小さい順
//priority_queue<int, vector<int>, greater<int>> c,c.top()
//map<int, int> M1; 変数[key] = value; 変数.erase(key); 変数.at(key); 変数.count(key)所属判定　変数.size()
//find(all(x), key)boolソート済みのベクトル
//*lower_bound(all(x),k)以上の最小の要素,*uppper_bound(all(x),k)より大きい最小の要素
//char('0'+cnt) 数字cntからcharへの変換
//int(char-'0') charからintへの変換

int main(){
    int n,m;
    cin >> n >> m;
    vi h(n);
    rep(i,n){
        cin >> h.at(i);
    }

    vb ok(n,true);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        
        if(h.at(a) <= h.at(b)) ok.at(a) = false;
        if(h.at(a) >= h.at(b)) ok.at(b) = false;
    }
    cout << count(all(ok),true) << endl;

}


Measured memory_bytes: 3796
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_map>

using namespace std;

const double pi=4*atan(1.0);

int mod=1000000007;

int main() {
	int n,W;
	cin>>n>>W;
	vector<int> w(n);
	vector<int> v(n);
	vector<vector<int>> dp(n+1,vector<int>(W+1));
	for(int i=0;i<n;++i){
		cin>>v[i]>>w[i];
	}
	for(int j = 0; j <= W; j++) {
		dp[n][j] = 0;
	}
	for(int i = n - 1; i >= 0; i--) {
		for(int j = 0; j <= W; j++) {
			if(j < w[i])
				dp[i][j] = dp[i + 1][j];
			else
				dp[i][j] = max(dp[i + 1][j],dp[i + 1][j - w[i]] + v[i]);
		}
	}
	cout << dp[0][W] << endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 6844
N,M = map(int,input().split())
gateid = [list(map(int,input().split())) for i in range(M)]
idleft = max(gateid,key=lambda x:x[0])
idright = min(gateid,key=lambda x:x[1])
ans = idright[1]-idleft[0]+1
if ans<0:
  ans = 0
print(ans)

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

int main(){
  
  long int x;
  cin >> x;
  
  cout << x*(x+1)/2 - 3*(x/3)*(x/3+1)/2 - 5*(x/5)*(x/5+1)/2 + 15*(x/15)*(x/15+1)/2 << endl;
  
  return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if((n%10)==7)
        cout<<"Yes"<<endl;
    else if ((n/10)%10==7)
        cout<<"Yes"<<endl;
    else if ((n/100)%10==7)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
        return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define trav(x, a) for (auto& x: a)

const int MX  = 2e5+5;
const int MOD = 1e9+7;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

int main() {

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

    string A,B,C; cin >> A >> B >> C;

    bool res = (A[sz(A)-1] == B[0] && B[sz(B)-1] == C[0]);

    cout << ((res) ? "YES" : "NO");

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 202333
using namespace std;
char s[maxn];
int main() {
	int n = 0;
	scanf("%s", s);
	for(char *S = s; *S; ++S) {
		n += (*S - '0');
	}
	puts(n % 9 == 0 ? "Yes" : "No");
	return 0;
}

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

int main() {
    long long int n,k;
    cin>>n>>k;
    int a[n];
    int poss = false;
    int maxa = INT_MIN;
    int gcda = 0;
    for(int i = 0;i<n;i++){
        cin>>a[i];
        if(i == 0){
            gcda = a[i];
        } else {
            gcda = __gcd(gcda, a[i]);
        }
        if (a[i] > maxa) {
          maxa = a[i];
        }
        if(a[i] == k){
            poss = true;
        }
    }
    for(int i = 0;i <= maxa/gcda;i++){
        if((maxa - (i * gcda))==k){
            poss = true;
        }
    }
    if(poss == false){
        cout<<"IMPOSSIBLE"<<endl;
    } else {
        cout<<"POSSIBLE"<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>

int main(){
   int A, B;
   std::cin >> A >> B;
   std::string S;
   std::cin >> S;
   bool flag = true;
   for (int i=0; i<A+B+1; ++i){
      if (i == A){
         if (S.at(i) != '-'){
            flag = false;
         }
      }else {
         if (S.at(i) == '-'){
            flag = false;
         }
      }
   }
   if (flag)
      std::cout << "Yes" << std::endl;
   else
      std::cout << "No" << std::endl;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#define F first
#define S second
using namespace std;
using namespace boost::multiprecision;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  ll X,K,D;
  cin >> X >> K >> D;
  ll ans = 0;
  if (X < 0) {
    X = -X;
  }
  if (X/D <= K) {
    K -= (X/D);
    if (K % 2 == 0) {
      ans = X%D;
    } else {
      ans = abs((X%D) - D);
    }
  } else {
    ans = X - (D*K);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(){
    string S;
    cin >> S;
    vector<int> v('Z' - 'A' + 1,0);
    for (int i = 0; i < 4; i++)
    {
        v[S[i] - 'A']++;
    }
    for(int V :v)
    {
        if (V == 1 || V > 2)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
# dp[i日目][i-1日目にどれを選んだか] = i日目までの最大の幸福度
import sys
sys.setrecursionlimit(10 ** 8)

n = int(input())
a, b, c = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

dp = [[-1 for _ in range(3)] for _ in range(n + 1)]
for i in range(3):
    dp[0][i] = 0


def rec(i, choice):
    if dp[i][choice] > 0:
        return dp[i][choice]
    if i == n:
        return 0
    ret = 0  # ループじゃなくてifでやってるのでそれぞれ確実に大きい値が入る（ので更新する必要がない）
    if choice == 0:
        ret = a[i] + max(rec(i + 1, 1), rec(i + 1, 2))
    elif choice == 1:
        ret = b[i] + max(rec(i + 1, 0), rec(i + 1, 2))
    elif choice == 2:
        ret = c[i] + max(rec(i + 1, 0), rec(i + 1, 1))
    dp[i][choice] = ret
    return ret


print(max(rec(0, 0), rec(0, 1), rec(0, 2)))


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

int main(){
	int H,W,N;
	int cMap[1013][1013];
	int Map[1013][1013];
	while(cin >> H >> W >> N && H && W && N){
	    for(int i=0;i<H+3;i++)for(int J=0;J<W+3;J++)cMap[J][i] = 0;
	    if(H+W+N == 0)break;
	    for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
		  cin >> Map[i][j];
		}
	    }
	    cMap[1][1] = N;//奇数ならそのまま偶数なら別
	    for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){

		    cMap[i][j+1] += cMap[i][j]/2; 
		    cMap[i+1][j] += cMap[i][j]/2;
		    if(cMap[i][j]%2 != 0 ){
			if(Map[i][j] == 1){
			    cMap[i][j+1]++;
			}
			else {
			    cMap[i+1][j]++;
			}
		    }
		}
	    }
	  
	    int x,y;
	    x = y = 1;
	    while(1<= y && y <= H && 1<= x && x<= W){
		if(cMap[y][x]%2 == 0){
		    if(Map[y][x] == 1)y++;
		    else x++;
		}
		else{
		    if(Map[y][x] == 1)x++;
		    else y++;
		    
		}
	    }
	    cout << y << " " << x << endl;

	}



  return 0;
}

Measured memory_bytes: 8804
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

vector<pair<ll, ll>> primeFactorization(ll n) {
    vector<pair<ll, ll>> result;
    for (ll i = 2; i * i <= n; i++) {
        ll num = 0;
        while (n % i == 0) {
            n /= i;
            num++;
        }
        if (num != 0) {
            result.push_back({ i, num });
        }
    }

    if (n != 1) {
        result.push_back({ n, 1 });
    }

    return result;
}

int main() {
    ll N, P;
    cin >> N >> P;
    auto p = primeFactorization(P);
    ll ans = 1;
    for (auto e : p) {
        ans *= pow(e.first, e.second / N);
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
	int a[100],i,n,sum = 0;
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		a[i] = i + 1;
		sum = sum + a[i];
	}
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 128
A,B,C = list(map(int, input().split()))

if A==B==C:
  if A%2==0:
    answer = -1
  else:
    answer = 0
  
else:
  answer = 0
  while A%2==B%2==C%2==0:
    A,B,C = (B+C)//2, (A+C)//2, (A+B)//2
    answer += 1

print(answer)

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
using ll = long long;
using ull = unsigned long long;
constexpr int MOD = 1000000007;

int mod(int x){
	return x % MOD;
}

int main(void)
{
    IOS
    int n;cin >> n;
    vector<pair<int,int>> v(n);
    REP(i,n) {
        int x,y;cin >> x>>y;
        v[i] = make_pair(y,x);
    }
    sort(ALL(v));

    int t=0;
    REP(i,n) {
        t += v[i].second;
        //cerr << t << endl;
        if (t > v[i].first) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

int main() {
  //
  ll n;
  cin >> n;
  vl h(n);
  rep(i, n) cin >> h[i];
  for (int i = n - 2; i >= 0; i--) {
    if (h[i] <= h[i + 1]) continue;
    if (h[i] == h[i + 1] + 1) {
      h[i] = h[i + 1];
    } else {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int ans=0,a,b;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='A'){
			a=i;
			break;
		}
	}
	for(int i=0;i<s.size();i++){
		if(s[i]=='Z'){
			b=i;
		}
	}
	cout<<b-a+1<<endl;
  return(0);
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int n, a, x = 0, y = 0;
  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    scanf("%d", &a);
    x += a*a;
    y += a;
  }
  a = y/n + (y%n > n/2);
  printf("%d\n", x + (n*a - 2*y)*a);
}


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

int A, B, C;

int main()
{
  #ifdef OJ
    freopen("/home/linjian/Documents/cpp_programs/in.txt", "r", stdin);
  #endif
  cin >> A >> B >> C;
  for (int i = 1; i <= B; ++i) {
    if (i * A % B == C) {
      puts("YES");
      return 0;
    }
  }
  puts("NO");
  return 0;
}

Measured memory_bytes: 256
//A - On the Way
#include <bits/stdc++.h>
using namespace std;
template<size_t SIZE, class T> inline size_t array_size(T (&arr)[SIZE]) {
    return SIZE;
}
int main() {
    int N;
    string S;
#if 0
  	std::ifstream in("input.txt");
  	std::cin.rdbuf(in.rdbuf());
#endif
    cin>>N>>S;
    int least = INT_MAX;
    int num_l_b=0; //左,黒
    int num_r_w=0; //右,白
    //白の数
    for (int i=0;i<N;++i) {
        if (S[i]=='.') ++num_r_w;
    }
    least = num_l_b + num_r_w;
    for (int i=0;i < N;++i) {
        //0,#####
        //1,.####
        //2,..###
        //3,...##
        //4,....#
        //5,.....
        int num =0;
#if 1
        if(S[i]=='#'){
            num_l_b++;
        } else {
            num_r_w--;
        }
        num = num_l_b + num_r_w;
#else
        for(int j=0;j<N;++j){
            if(j >= i){
				if(S[j] != '#') {
					++num;
				}
			} else {
				if(S[j] != '.') {
					++num;
				}
            }
        }
#endif
        least = std::min(least,num);
    }
	cout << least << endl;
	return 0;
}

Measured memory_bytes: 640
A, B = [int(i) for i in input().split()]
str_A = bin(A)[2:]
str_B = bin(B)[2:]
max_len = max(len(str_A), len(str_B))
A += 1
B += 1
result = ""
"""
a = A % 4
b = B % 4
if a % 2 == 0:
    if a == b:
        result += "1"
    else:
        result += "0"
else:
    if max(a,b) - min(a,b) == 3:
        result += "0"
    else:
        result += "1"
"""
if (B // 2 - (A-1) // 2) % 2 == 0:
    result += "0"
else:
    result += "1"
"""
for i in range(2,max_len+1):
    a = A % 2 ** i
    b = B % 2 ** i
    if a < 2 ** (i - 1):
        a = 2
    else:
        a = 2 ** i - a + 1
    if b < 2 ** (i - 1):
        b = 2
    else:
        b = b - 2 ** (i - 1)
    if (a + b) % 2 == 0:
        result += "0"
    else:
        result += "1"
"""
for i in range(2, max_len+1):
    a = (A-1) % 2 ** i
    a = 0 if a < 2 ** (i - 1) else 2 ** i - a
    b = B % 2 ** i
    b = 0 if b < 2 ** (i - 1) else b - 2 ** (i - 1)
    if (b + a) % 2 == 0:
        result += "0"
    else:
        result += "1"
print(int(result[::-1],2))


Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
from collections import *

S = input()[:-1]
K = int(input())
l = []

for i in range(len(S)):
    for j in range(i, min(len(S), i+5)):
        l.append(S[i:j+1])

l = list(set(l))
l.sort()
print(l[K-1])

Measured memory_bytes: 41072
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=200010;
const ll mod=1e9+7;

int main(){
  int n,k;  cin >> n >> k;
  vector<ll> v(n);
  rep(i,n){ cin >> v[i]; }
  ll ans=0;
  for(int a=0; a<=min(n,k); a++){ for(int b=0; a+b<=min(n,k); b++){
    ll cur=0;
    vector<ll> t;
    rep(i,a){ t.emplace_back(v[i]); cur+=v[i]; }
    rep(i,b){ t.emplace_back(v[n-1-i]); cur+=v[n-1-i]; }
    
    sort(t.begin(),t.end());
    for(int i=0; i<min(k-a-b,(int)t.size()); i++){
      if(t[i]<0){cur -= t[i];}
    }
    ans = max(ans,cur);
  }}

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

Measured memory_bytes: 256