akhauriyash/Code-Regression huggingface dataset:
#include<iostream>

int dfs(int now, int n, int m, bool*arr, bool*use) {
	bool flag = true;

	for (int i = 0; i < n; i++) {
		if (use[i] == false)flag = false;
	}
	if (flag)return 1;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (arr[now * n + i]&&use[i]==false) {
			use[i] = true;
			ans += dfs(i, n, m, arr, use);
			use[i] = false;
		}
	}
	return ans;
}

int main() {
	int n, m;
	std::cin >> n >> m;
	bool *arr =new bool[n*n];
	bool *use = new bool[n];
	for (int i = 0; i < n; i++)use[i] = false;
	for (int i = 0; i < n*n; i++)arr[i] = false;
	for (int i = 0; i < m; i++) {
		int a, b;
		std::cin >> a >> b;
		a--; b--;
		arr[b*n + a] = true;
		arr[a*n+ b] = true;
	}
	use[0] = true;
	printf("%d", dfs(0,n, m, arr, use));
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc093/tasks/arc094_a
a, b, c = map(int, input().split())

nums = [a, b, c]
nums.sort()

ans = 0
if (nums[1] - nums[0]) % 2 == 1:
    # 小さい2つの差が奇数の場合、偶数になるように
    # 小さい2つの数字両方にならないように、1を足す。
    # ここでは、二番目に大きいのと、最大の数に1を足す。
    nums[1] += 1
    nums[2] += 1
    ans += 1
ans += (nums[1] - nums[0]) // 2 # 一番小さい数が、二番目に大きい数に追いつくようにする。それには2ずつ足すのが良い。
ans += (nums[2] - nums[1]) # 一番目も二番目も同じかずになったので、両方に１つづ足していき、最大の数と同じになる様にする。
print(ans)


Measured memory_bytes: 38256
N = int(input())
s = [input() for i in range(N)]

alphabets = 'abcdefghijklmnopqrstuvwxyz'

ans = ''
for c in alphabets:
    min_count = float('inf')
    for s_i in s:
        count = s_i.count(c)
        if count < min_count:
            min_count = count
    ans += c * min_count
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1LL<<60;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::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; }
using namespace std;

int N;
int a[200010], t[200010];

int main() {
    cin >> N;
    rep(i, N) {
        cin >> a[i];
        t[i] = a[i];
    }
    sort(a, a+N);

    rep(i, N) {
        if (t[i] < a[N/2]) cout << a[N/2] << endl;
        else cout << a[N/2 - 1] << endl;
    }
}


Measured memory_bytes: 3712
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")

Measured memory_bytes: 166868
// スタックサイズ: 100MB

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <random>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }




int main() {
	fastio;
	
	int A, B;
	cin >> A >> B;

	int ans = -1;
	for (int i = 1; i <= 100000; ++i) {
		if (floor((double)i * 0.08) == A && floor((double)i * 0.10) == B) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

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

	int d;
	cin >> d;
	string s ;
	if(d == 25)
		s = "Christmas";
	if(d == 24)
		s = "Christmas Eve";
	if( d == 23)
		s = "Christmas Eve Eve";
	if (d == 22)
		s = "Christmas Eve Eve Eve";
	cout << s;


	return 0;
}

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

int main()
{
    int a, b, c, d;
    int ans = 0;
    std::cin >> a >> b >> c >> d;
    for (int i = std::min(a, c); i <= std::max(b, d); ++i) {
        if (a <= i && i <= b && c <= i && i <= d) {
            ++ans;
        }
    }
    if (ans > 0) {
        --ans;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <numeric>
#include <iterator>
#include <unordered_map>
#include <array>
#include <map>
#include <cstring>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctgmath>
#include <set>
#include <queue>

using namespace std;

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;

	vector<long long> all;

	for (int i = 0; i < n; i++)
	{
		long long t;
		cin >> t;

		all.push_back(t);
	}

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

	long long mini = 99999999999;

	for (int i = 0; i < n - k+1; i++)
	{
		mini = min(mini, all[i + k-1] - all[i]);
	}
	cout << mini << "\n";
}



Measured memory_bytes: 1400
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
 
using namespace std;
 
typedef pair<const int,const int> P;
typedef pair<const string,P> PP;
 
map<const string,int> solve()
{
	map<const string,int> d;
	queue<PP> q;
	string t;
	q.push(PP("01234567",P(0,0)));
	while(!q.empty())
	{
		PP p = q.front(); 
		q.pop();
		string str = p.first;
		int n = p.second.first+1;
		int b = p.second.second;
		d[str] = n;
		if(b && b != 4)
		{
		  t = str;
		  swap(t[b],t[b-1]);
		  if(!d[t]) q.push(PP(t,P(n,b-1)));
		}
		if(b != 3 && b < 7)
		{
		  t = str;
		  swap(t[b],t[b+1]);
		  if(!d[t]) q.push(PP(t,P(n,b+1)));
		}
		if(b<4)
		{
		  t = str;
		  swap(t[b],t[b+4]);
		  if(!d[t]) q.push(PP(t,P(n,b+4)));
		}
		else
		{
		  t = str;
		  swap(t[b],t[b-4]);
		  if(!d[t]) q.push(PP(t,P(n,b-4)));
		}
	}
	return d;
}
 
int main(void)
{
  map<const string,int> d = solve();
  string str;
 
  while(getline(cin,str))
  {
	string t;
	for(int i = 0; i < str.size(); i++)
	{
		if(str[i]!=' ')
		{
			t+=str[i];
		}
	}
	cout << d[t]-1 << endl;
  }
  return 0;
}

Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int pre[20][100002];


ll cal(int a, int b){
    ll days = 0;
    while(true){
        if(a == b) return days;

        int k = 0;
        while(pre[k][a]<b) k++;

        if(k==0) return days+1LL;
        else {
            a = pre[k-1][a];
            days+=(1LL << (k-1));
        }
    }
}


int main(){
    int n,l,q;
    cin>>n;
    vector<pair<int,int>> arr;
    vector<int> mp(n+1);
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        int t;cin>>t;
        x[i] = t;
        arr.push_back({t,i});
        mp[i] = t;
    }

    sort(arr.begin(),arr.end());
    sort(x.begin(),x.end());
    cin>>l>>q;

    for(int i = 0; i < n; i++){
        pre[0][i] = upper_bound(x.begin(),x.end(),x[i]+l) - x.begin();
        pre[0][i]-=1;
    }

    int k = 0;
    while(n>>k > 0) k++;

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

    while(q--){
        int a,b;cin>>a>>b;
        int ai,bi;
        a--;b--;
        ai = mp[a],bi = mp[b];
        if(ai>bi) swap(ai,bi);
        
        a = lower_bound(x.begin(),x.end(),ai) - x.begin();
        b = lower_bound(x.begin(),x.end(),bi) - x.begin();
        
        ll days = cal(a,b);
        cout<<days<<endl;;

    }
    

}


Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(n,v) cout<<#v<<":";for(int i=0;i<n;i++)cout<<v[i]<<" ";cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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,k;
    cin>>n>>k;
    string s;
    cin>>s;
    /*
    最初に幸福度数える
    真ん中ひっくり返せば幸福度+2
    端ひっくり返せば幸福度+1
     */
    int base=0;
    for(int i=0;i<n-1;i++){
        if(s[i]=='R'&&s[i+1]=='R') base++;
    }
    for(int i=n-1;i>0;i--){
        if(s[i]=='L'&&s[i-1]=='L') base++;
    }
    if(base==n-1){
        cout<<base<<endl;return 0;
    }
    //lについて内側何個ありますか
    int hasi=0,naka=0,idx=0;
    if(s[0]=='L') hasi++;
    while(s[idx]=='L') idx++;
    while(idx<n){
        char tmp=s[idx];int cnt=0;
        while(s[idx]==tmp&&idx<n){
            idx++;
        }
        if(idx==n&&tmp=='L') hasi++;
        else if(tmp=='L') naka++;
    }
    int ans1=base;
    rep(i,k){
        if(naka==0&&hasi==0) break;
        else if(naka>0){
            ans1+=2;naka--;
        }
        else if(naka==0&&hasi>0){
            ans1+=1;hasi--;
        }
    }

    //rについて内側何個ありますか
    hasi=0,naka=0,idx=0;
    if(s[0]=='R') hasi++;
    while(s[idx]=='R') idx++;
    while(idx<n){
        char tmp=s[idx];int cnt=0;
        while(s[idx]==tmp&&idx<n){
            idx++;
        }
        if(idx==n&&tmp=='R') hasi++;
        else if(tmp=='R') naka++;
    }
    int ans2=base;
    rep(i,k){
        if(naka==0&&hasi==0) break;
        else if(naka>0){
            ans2+=2;naka--;
        }
        else if(naka==0&&hasi>0){
            ans2+=1;hasi--;
        }
    }
    cout<<(max(ans1,ans2))<<endl;
    return 0;
}

Measured memory_bytes: 512
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    L, R, d = MI()
    ans = 0
    for i in range(L, R+1):
        if i%d == 0:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9188
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define debug int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<ll> VE;
const ll mod = 1e9 + 7; //10^9+7

int main(){
    string s;
    cin >> s;
    if(s.size() == 2){
        print(s);
    }else{
        RREP(i, s.size()){
            cout << s[i];
        }
        print("");
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
   int main()
   {
       int X, A, B;
       cin >> X >> A >> B;
       if (B <= A) {
           cout << "delicious" << endl;
       } else {
           if (X + A - B >= 0) {
               cout << "safe" << endl;
           } else {
               cout << "dangerous" << endl;
           }
       }
    }

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

using namespace std;
using namespace __gnu_pbds;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
#define oset tree<int, null_type,greater<int>, rb_tree_tag,tree_order_statistics_node_update>


int main()
{
    int po[21];
    po[0] = 1;
    for(int i=1; i<21; i++){
        po[i] = po[i-1]<<1;
    }
    int l;
    cin >> l;

    int n = log2(l);
    n++;
    int m = n-1, lg;
    int ll = l;
    lg = log2(l);
    m += lg;
    l -= po[lg];

    while(l){
        lg = log2(l);
        m++;
        l -= po[lg];
    }

    cout << n << " " << m << "\n";
   // int ccc = 0;

    for(int i=1; i<n; i++){
        //printf("%d %d 0\n", i, i+1);
        cout << i << " " << i+1 << " 0\n";
        //ccc++;
    }

    l = ll;
    lg = log2(l);
    lg = po[lg];
    int i;

    for(i=0; po[i]<lg; i++){
        //printf("%d %d %d\n", i+1, i+2, po[i]);
        cout << i+1 << " " << i+2 << " " << po[i] << "\n";
        //ccc++;
    }

    l -= lg;
    i = po[i];
    while(l){
        lg = log2(l);
        //printf("%d %d %d\n", lg+1, n, i);
        cout << lg+1 << " " << n << " " << i << "\n";
        //ccc++;
        l -= po[lg];
        i += po[lg];
    }
    //cout << ccc << endl;

    return 0;
}


Measured memory_bytes: 640
N = int(input())
a = list(input().split())
A = [int(a[i]) for i in range(N)]
count_4 = 0
count_2 = 0
count_o = 0

for i in range(N):
    if A[i] % 4 == 0:
        count_4 += 1
    elif A[i] % 2 == 0:
        count_2 += 1
    else:
        count_o += 1

if count_4 < count_o + (1 if count_2 >= 1 else 0) - 1:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 14864
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    double a, b;
    cin >> a >> b;

    double ret = a * b / 3.305785;
    printf("%.10f\n", ret);

    return 0;
}

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

typedef long long ll;
typedef pair <ll, ll> pii;

const ll MAX_N = 1e5 + 5, inf = 1000000LL * 1000000LL * 1000000LL;
ll n, ans, id = -1, f = inf, ID = -1;
ll down[MAX_N];
vector <pii> G[MAX_N];

ll dfs1 (ll v = 0, ll p = 0) {
    down[v] = 1;
    for (pii u: G[v])
        if (u.first != p)
            down[v] += dfs1(u.first, v);

    return down[v];
}

void dfs2 (ll v = 0, ll p = 0) {
    for (pii u: G[v])
        if (u.first != p) {
            dfs2(u.first, v);

            ans += u.second * min(down[u.first], n - down[u.first]) * 2LL;
            if (down[u.first] == n - down[u.first])
                ID = u.second;
        }
}

void dfs3 (ll v = 0, ll p = 0) {
    id = v;
    for (pii u: G[v])
        if (u.first != p && down[u.first] >= ((n + 1) / 2))
            dfs3(u.first, v);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (ll i = 0; i < n - 1; i++) {
        ll v, u, w;
        cin >> v >> u >> w;
        v--, u--;

        G[v].push_back({u, w});
        G[u].push_back({v, w});
    }

    dfs1();
    dfs2();
    dfs3();

    if (ID != -1) {
        cout << ans - ID << "\n";
        return 0;
    }
    
    for (pii p: G[id])
        f = min(f, p.second);

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

Measured memory_bytes: 13952
#include<cstdio>
#include<algorithm>
using namespace std;


int main(){
  int n,m,white[50],blue[50],red[50];
  scanf("%d %d",&n,&m);
  for(int i=0;i<n;i++){
    white[i] = 0;
    blue[i] = 0;
    red[i] = 0;
    for(int j=0;j<m;j++){
      char c;
      scanf(" %c",&c);
      if(c=='W') white[i]++;
      else if(c=='B') blue[i]++;
      else if(c=='R') red[i]++;
    }
  }
  int ans = 2500;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n-1;j++){
      int x = 0;
      for(int k=0;k<n;k++){
        if(k<=i) x+=m-white[k];
        else if (k<=j) x+=m-blue[k];
        else x+=m-red[k];
      }
      ans = min(ans,x);
    }
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 2700
H,W=map(int,input().split())
Grid=[]
for _ in range(H):
  Grid.append(list(input()))
tmp=0
ans=0
up=[[0 for _ in range(W)] for _ in range(H)]
down=[[0 for _ in range(W)] for _ in range(H)]
left=[[0 for _ in range(W)] for _ in range(H)]
right=[[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if Grid[i][j]=='.':
      left[i][j]=left[i][j-1]+1
      up[i][j]=up[i-1][j]+1
    if Grid[H-i-1][j]=='.':
      down[H-i-1][j]=down[-i][j]+1
    if Grid[i][W-j-1]=='.':
      right[i][W-j-1]=right[i][-j]+1
      
for i in range(H):
  for j in range(W):
    ans=max(ans,left[i][j]+up[i][j]+down[i][j]+right[i][j]-3)
print(ans)    

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

int main() {
	string a;
	string b;
	cin>>a;
	cin>>b;
	int cnt=0;
	for(int i=0;i<a.length();i++)
	{
	    if(a[i] != b[i])
	    {
	        cnt++;
	    }
	}
	cout<<cnt;
	return 0;
}


Measured memory_bytes: 3820
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#define MIN(a,b) (((a)<(b)) ? (a) : (b))
#define MAX(a,b) (((a)>(b)) ? (a) : (b))

bool Leap_Year(int n)
{
  if(n%4 == 0)
    {
      if(n%100 == 0)
	{
	  if(n%400 == 0) return true;
	  else return false;
	}
      return true;
    }
  else return false;
}

int main()
{
  int a,b;
  bool put = false;
  while(1)
    {
      scanf("%d%d",&a,&b);
      if(a == 0 && b == 0) break;
      int i;
      bool flag = true;
      if(put) printf("\n");
      for(i = a; i <= b; i++)
	{
	  if(Leap_Year(i))
	    {
	      printf("%d\n",i);
	      flag = false;
	    }
	}
      if(flag) printf("NA\n");
      put = true;
    }
  return 0;
}

Measured memory_bytes: 616
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int res = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int x = Integer.parseInt(str[2]);
        int[] nums = new int[m];
        int[][] books = new int[n][m+1];
        for(int i=0; i<n; ++i) {
            str = br.readLine().split(" ");
            //System.out.println(Arrays.toString(str));
            for (int j = 0; j <= m; j++) {
                books[i][j] = Integer.parseInt(str[j]);
            }
        }
        dfs(0,0,nums,books,n,m,x);
        if(res == 2147483647){
            System.out.println(-1);
        }else{
            System.out.println(res);
        }
    }
    public static void dfs(int idx, int cost,int[] nums, int[][] books, int n, int m, int x){
        //System.out.println(idx + " " + cost + " " + Arrays.toString(nums));
        if(idx == n){
            boolean ok = true;
            for(int i=0; i<m; ++i){
                if(nums[i] < x){
                    ok =false;
                    break;
                }
            }
            if(ok){
               //System.out.println(cost);
               res = Math.min(res, cost);
            }
            return;
        }
        cost += books[idx][0];
        for(int i=1; i<=m; ++i){
            nums[i-1] += books[idx][i];
        }
        dfs(idx+1,cost,nums,books,n,m,x);
        cost -= books[idx][0];
        for(int i=1; i<=m; ++i){
            nums[i-1] -= books[idx][i];
        }
        dfs(idx+1,cost,nums,books,n,m,x);
    }
}


Measured memory_bytes: 33804
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e16;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll N; cin >> N;
    set<ll> uq; map<ll, ll> cnt;
    REP(i, N){
        ll a; cin >> a; uq.insert(a); cnt[a]++;
    }
    ll ecnt = 0;
    FORMAP(it, cnt){
        if(it->ss%2 == 0) ecnt++;
    }
    ll ans = uq.size();
    if(ecnt%2 != 0) ans--;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
#define INF           1e9
#define INFL          static_cast<lint>(INF)
#define REP(i,n)      for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)     for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)     for(lint i=n-1;i>=0;--i)
#define REPR1(i,n)    for(lint i=n;i>0;--i)
#define REPI(i,ini,n) for(lint i=(ini),i##_len=(n);i<i##_len;++i)
#define REPC(i,obj)   for(auto i:obj)
#define R_UP(a,b)     (((a)+(b)-1)/(b))
#define ALL(obj)      (obj).begin(),(obj).end()
int main()
{
	multimap<string, int>m;
	int q = in();
	REP(i, q)
	{
		int n = in();
		string key;
		int x;
		switch (n)
		{
		case 0:
			key = in<string>();
			x = in();
			m.insert(make_pair(key, x));
			break;
		case 1:
			key = in<string>();
			for (auto p = m.equal_range(key); p.first != p.second; p.first++)cout << p.first->second << endl;
			break;
		case 2:
			key = in<string>();
			m.erase(m.equal_range(key).first, m.equal_range(key).second);
			break;
		case 3:
			string l = in<string>(), r = in<string>();
			for (auto itr1 = m.lower_bound(l), itr2 = m.upper_bound(r); itr1 != itr2; itr1++)cout << itr1->first << ' ' << itr1->second << endl;
			break;
		}
	}
}


Measured memory_bytes: 24812
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)


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


ll dist[2600];
int main()
{
  ll N, M, P; cin >> N >> M >> P;
  vector<vector<pair<ll, ll>>> v(N);
  REP(i, M) {
    ll a, b, c; cin >> a >> b >> c;
    a--; b--;
    v[a].PB(MP(b, c-P));
  }

  REP(i, N) dist[i] = -LLINF;
  dist[0] = 0;

  REP(cnt, N) {
    REP(from, N) {
      if (dist[from] == -LLINF) continue;
      for (auto e : v[from]) {
        int to, cost;
        tie(to, cost) = e;
        if (dist[to] < dist[from] + cost) {
          dist[to] = dist[from] + cost;
        }
      }
    }
  }

  vector<bool> ng(N, false);
  REP(cnt, N) {
    REP(from, N) {
      if (dist[from] == -LLINF) continue;
      for (auto e : v[from]) {
        int to, cost;
        tie(to, cost) = e;
        if (dist[to] < dist[from] + cost) {
          dist[to] = dist[from] + cost;
          ng[to] = true;
        }
        if (ng[from]) ng[to] = true;
      }
    }
  }

  if (ng[N-1]) cout << "-1" << endl;
  else cout << max(dist[N-1], 0LL) << endl;

  return 0;
}

Measured memory_bytes: 512
while True:
    m, f, r = map(int, input().split())
    if m == -1 and f == -1 and r == -1:
        break
    
    score = m + f
    
    if (m == -1 or f == -1) or (score < 30):
        print("F")
    elif score < 50:
        if r >= 50:
            print("C")
        else:
            print("D")
    elif score < 65:
        print("C")
    elif score < 80:
        print("B")
    else:
        print("A")
    

    


Measured memory_bytes: 5592
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (Integer.parseInt(sc.next()) >= K) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 45736
#include <bits/stdc++.h>
#include <unistd.h>
#include <stdio.h>
using namespace std;
typedef long long lli;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define forr(c, n) for (int i = c; i < n; i++)
#define forli(n) for (lli i = 0; i < n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())

//FUNCTONS
lli llipower(lli x, lli y)
{
    lli res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x);
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
lli llipowerp(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli gcd(lli a, lli b)
{
    if (!a)
        return b;
    return gcd(b % a, a);
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
void printvec(vector<T> inp)
{
    for (int i = 0; i < inp.size(); i++)
    {
        cout << inp[i] << " ";
    }
    cout << endl;
}
template <typename T>
T ceildiv(T x, T y) { return 1 + ((x - 1) / y); }
lli modInverse(lli a, lli m)
{
    lli g = gcd(a, m);
    if (g != 1)
        return -1;
    else
        return llipowerp(a, m - 2, m);
}

int main()
{
    lli k;
    cin>>k;
    lli count=0;
    lli curr=1;
    string s;
    vector<lli> ans;
    bool con;
    lli exp;
    
    while(count<(long long)(100000)){
        // if(breakn++>20) break;

        //cout<<curr<<endl;
        s = to_string(curr);
        con = true;
        
        fori(s.size() - 1)
        {
            if (s[i] - s[i + 1]> 1)
            {
                con = false;
                exp = llipower(10, s.size() - i - 2);
                //cout<<curr<<" "<<exp<<" "<<curr%exp<<" "<<s[i]<<" "<<s[i+1]<<" i"<<i<<endl;
                curr-=(curr%exp);
                curr += exp;
                break;
                
            }
            else if(s[i+1]-s[i]>1){
                con=false;
                exp = llipower(10, s.size() - i - 1);
                //cout << curr << " " << exp << " " << curr % exp << " " << s[i] << " " << s[i + 1] << " i" << i << endl;
                curr -= (curr % exp);
                curr += exp;
                break;
            }
            

        }
        if(con){
            ans.pb(curr);
            count++;
            curr++;
        }
        

    }
    //fori(1000) cout<<ans[i]<<" ";
    cout<<ans[k-1]<<endl;





}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define _GLIBCXX_DEBUG
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#pragma GCC optimize("Ofast")
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using vvli = vector<vlli>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
// aよりもbが大きいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T &b)
{
  if (a > b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli a, b, c, x, y, h, k, n, w, ans = 0, tmp = 0, count = 0;
  string s, t;
  vector<pair<string, pair<lli, lli>>> pr;
  cin >> x >> y;
  set<lli> d;
  // count = x;
  ans = x * 2;
  tmp = x * 4;
  // tmp = (x - 1) * 4 + 2;
  // d.insert(tmp);
  // for (auto g : d)
  // {
  //   cout << g << endl;
  // }
  if (y <= tmp && y % 2 == 0 && y >= ans)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3624
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <conio.h>
using namespace std;

typedef long long int ll;
typedef pair<ll,ll> pll;

#define rep(i,n)	for(ll i=0;i<(n);i++)
#define SZ(x) ((ll)x.size())
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define F first
#define S second
#define int ll
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// const ll MOD = INT_MAX;
const double PI = acos(-1);

void openfile(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}

const int N = 3005;
const int mod = 1e9+7;
char s[N];
int dp[N][N];
// dp(i,j) - the number of ways to put numbers in prefix of size 'i'
// such that the last number is j

void add(int &a,int b){
	a += b;
	if(a >= mod)	a -= mod;
}

signed main(){
	IOS
	int n;
	scanf("%lld", &n);
	scanf("%s", s);
	dp[1][1] = 1;
	for(int len = 2; len <= n; len++){
		for(int a = 1; a <= len; a++)	add(dp[len-1][a],dp[len-1][a-1]);	// compute prefix sums
		for(int b = 1; b <= len; b++){
			int L, R;
			if(s[len-2] == '<')	L = 1, R = b - 1;
			else				L = b, R = len - 1;

			// for(int i = L; i <= R; i++)	add(dp[len][b], dp[len-1][i]);	// prefix sum
			if(L <= R)	add(dp[len][b], (dp[len-1][R] - dp[len-1][L-1] + mod) % mod);

			// for(int a = 1; a <= len - 1; a++){
			// 	// previous pos
			// 	int real_a = a;
			// 	if(a >= b)	real_a++;
			// 	assert(real_a != b);
			// 	if((real_a < b) != (s[len-2] == '<'))	continue;
			// 	add(dp[len][b],dp[len-1][a]);
			// }
		}
	}
	int ans = 0;
	rep(i,n)	add(ans, dp[n][i+1]);
	printf("%lld\n", ans);
}


Measured memory_bytes: 69120
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;
 
#define SIZE (1E5)+1
 
int main(void)
{
	vector<bool> prime(SIZE, true);
	vector<int> cnt(SIZE, 0);
 
	prime[0] = false;
	prime[1] = false;
	for(int i=2; i<SIZE; i++){
		cnt[i] = cnt[i-1];
 
		if(prime[i] == false)
			continue;
 
		for(int j=i+i; j<SIZE; j+=i)
			prime[j] = false;
 
		if(prime[(i+1)/2] == true)
			cnt[i]++;
	}
 
	int Q;
	cin >> Q;
 
	for(int i=0; i<Q; i++){
		int l, r;
		cin >> l >> r;
 
		cout << cnt[r] - cnt[l-1] << endl;
	}
 
	return 0;
}


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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define endl '\n'

int main()
{
   /* #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    string s;
    cin>>s;
    vector<char> fro,dow;
    int q;
    cin>>q;
    int c=0;
    while(q--)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            c++;
        }
        else
        {
            int n;
            char ch;
            cin>>n>>ch;
            if(c&1)
            {
                if(n==1) n=2;
                else n=1;
            }
            if(n==1) fro.pb(ch);
            else dow.pb(ch);
        }
    }
    if(c&1) swap(fro,dow);
    if(c&1) reverse(all(s));
    reverse(all(fro));
    for(auto i:fro) cout<<i;
        cout<<s;
    for(auto i:dow) cout<<i;
    return 0;
}



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

int main(){
    int a,b,x;
    cin>>a>>b;
    x= a+b;
    if(b==0){
    cout<<a<<endl;
    }

    else if(x>=24){
    x=x-24;
    cout<<x<<endl;
}
   else if (x<24){
    cout<<x<<endl;
   }
}

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

/*
H * W <= 1e6なのでbfsすれば良い？
Kが10^6なので分岐が多すぎる
O(4 * 1e6)
*/

int	main(void)
{
	int h, w, k;
	cin >> h >> w >> k;
	int from_x, from_y, to_x, to_y;
	cin >> from_x >> from_y >> to_x >> to_y;
	from_x--; from_y--; to_x--; to_y--;
	vector<vector<bool>> grid(h, vector<bool>(w));
	vector<vector<int>> dfs(h, vector<int>(w, 1e9));
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			char c;
			cin >> c;
			grid[i][j] = (c == '.');
		}
	}
	queue<pair<int, int>> q;
	q.push({from_x, from_y});
	dfs[from_x][from_y] = 0;
	int depth = 0;
	int x, y;
	vector<int> dx = {1, -1, 0, 0};
	vector<int> dy = {0, 0, 1, -1};
	while (q.size())
	{
		depth++;
		int size = q.size();
		for (int i = 0; i < size; i++)
		{
			x = q.front().first;
			y = q.front().second;
			q.pop();
			if (x == to_x && y == to_y)
			{
				cout << depth - 1 << endl;
				return (0);
			}
			for (int j = 0; j < 4; j++)
			{
				for (int z = 1; z <= k; z++)
				{
					if (x + dx[j] * z < 0 || x + dx[j] * z >= h) break ;
					if (y + dy[j] * z < 0 || y + dy[j] * z >= w) break ;
					if (!grid[x + dx[j] * z][y + dy[j] * z]) break ;
					if (dfs[x + dx[j] * z][y + dy[j] * z] < depth) break ;
					if (dfs[x + dx[j] * z][y + dy[j] * z] == depth) continue ;
					dfs[x + dx[j] * z][y + dy[j] * z] = depth;
					q.push({x + dx[j] * z, y + dy[j] * z});
				}
			}
		}
	}
	cout << -1 << endl;
	return (0);
}


Measured memory_bytes: 11384
t,*S=*$<;i=1;p~(S.map{d=p=0;q=i;(d-=1;p|=r=s=p&q^q;q=0;(q|=S[-t.bit_length].to_i 2;s^=t)while(t=s&-s)>0;0<q&r&&x)while 0<q;i*=2;d}.min rescue 0)

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

long long n,m,o,p,nsum,msum,osum,psum;

int main(){
	cin>>n;
	m = n / 3;
	o = n / 5;
	p = n / 15;
	nsum = n * (n + 1) / 2;
	msum = 3 * m * (m + 1) / 2;
	osum = 5 * o * (o + 1) / 2;
	psum = 15 * p * (p + 1) / 2;
	cout<<nsum - msum - osum + psum<<endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N;
    string S;
    cin >> N >> S;

    vector<int> W(N + 1, 0), E(N + 1, 0);

    rep(i, N) {
        W[i + 1] = W[i] + (S[i] == 'W' ? 1 : 0);
    }
    for (int i = N - 1; i >= 0; i--) {
        E[i] = E[i + 1] + (S[i] == 'E' ? 1 : 0);
    }

    int ans = 1e9;

    rep(i, N) {
        int cp = W[i] + E[i + 1];
        chmin(ans, cp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3076
#include <vector>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>

using namespace std;

#define S 1000

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

    if(N <= S)
        cout << S - N << '\n';
    else if(N % S == 0){
        cout << 0 << '\n';
    } else {
        int nr =  N / S * S + S;
        cout << nr - N << '\n';
    }

    return 0;
}

Measured memory_bytes: 3596
N = int(input())
A = [int(x) for x in input().split()]
for i in range(N):
    for j in range(i, N):
        A[i], A[j] = A[j], A[i]
        if sorted(A) == A:
            print("YES")
            quit()
        A[i], A[j] = A[j], A[i]
print("NO")


Measured memory_bytes: 3060
import java.util.*

fun main(args: Array<String>) {
    val argList = Scanner(System.`in`)


    val n = argList.nextInt()
    val a = argList.nextInt()
    val b = argList.nextInt()

    val executor = TorT()
    val result = executor.execute(n, a, b)
    println(result)
}

class TorT {
    fun execute(n: Int, a: Int, b: Int): Int {
        val taxi = b
        val train = n * a

        if (taxi < train) {
            return taxi
        }
        return train
    }
}

Measured memory_bytes: 31396
#include <bits/stdc++.h>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ll long long
#define all(a) a.begin(), a.end() 
using namespace std;

int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  
  int num = 0;
  while(!(a<b)) {
    b *= 2;
    ++num;
  }
  while(!(b<c)) {
    c*= 2;
    ++num;
  }
  
  if(num <= k) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 3628
HP, n_magic = map(int,input().split())
attack_ls, power_taken_ls = [0]*(n_magic+1), [0]*(n_magic+1)
for i in range(n_magic):
    attack_ls[i+1], power_taken_ls[i+1] = map(int,input().split())
max_attack = HP + max(attack_ls)
dp = [[float('inf')]*(max_attack+1) for _ in range(n_magic+1)]
dp[0][0] = 0
for i in range(1,n_magic+1):
    for attack in range(max_attack+1):
        if attack - attack_ls[i] >= 0:
            dp[i][attack] = min(dp[i][attack], dp[i][attack-attack_ls[i]] + power_taken_ls[i])
        dp[i][attack] = min(dp[i-1][attack], dp[i][attack])
ans = float('inf')
for attack in range(HP, max_attack+1):
    ans = min(dp[n_magic][attack], ans)
print(ans)
        


Measured memory_bytes: 215992
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;
 
int n,m,ans=0;
//int tri[5005][5005];
vector<int> tri[5005];


int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=5003;i++){
		for(int j=0;j<=i+3;j++)tri[i].push_back(0);
	}
	for(int i=0;i<m;i++){
        int x,y,size;
        scanf("%d%d%d",&y,&x,&size);
        size++;
        tri[y][x]+=1;
        tri[y][x+1]-=1;
        tri[y+size][x]-=1;
        tri[y+size+1][x+1]+=1;
        tri[y+size][x+size+1]+=1;
        tri[y+size+1][x+size+1]-=1;
    }
    /*
    for(int i=1;i<=n+3;i++){
        for(int j=1;j<=i;j++){
            printf("%d%c",tri[i][j],i==j?'\n':' ');
        }
    }
    printf("o\n");
    */
    for(int i=2;i<=n;i++){
        for(int j=2;j<=i;j++){
            tri[i][j]+=tri[i][j-1];
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            printf("%d%c",tri[i][j],i==j?'\n':' ');
        }
    }
    printf("o\n");
    */
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            tri[j][i]+=tri[j-1][i];
        }
    }
    /*
    printf("o\n");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            printf("%d%c",tri[i][j],i==j?'\n':' ');
        }
    }
    */
    for(int i=1;i<=n;i++){
        int y=i+1,x=2;
        while(y<=n){
            tri[y][x]+=tri[y-1][x-1];
            y++,x++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(tri[i][j]>=1)ans++;
           // printf("%d%c",tri[i][j],i==j?'\n':' ');
        }
    }
    printf("%d\n",ans);
    return 0;
}

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

int main() {
	int n;
  	cin>>n;
  
  	vector <int> h(110);
  	rep(i,n){
    	cin>>h[i];
    }
  
  int ans=1;//一番目は必ず見えるから
  int highest=h[0];
  
  //2番目からループ
  for(int i=1;i<n;i++){
  	if(h[i]>=highest){
      ans++;
      highest=h[i];
      }	
   }
  
  cout<<ans<<endl;

}

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

dp = [0]*n
dp[0] = 0

for i in range(1,n):
    dp[i] = dp[i-1] + abs(h[i-1]-h[i])

    for j in range(2,k+1):
        if (i-j)>=0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

# print(dp)
print(dp[n-1])

Measured memory_bytes: 52448
def f(n):
    if n%2==0: return n//2
    else: return 3*n+1

N=int(input())
H=list(map(int,input().split()))

M=max(H)
tmp=0
ans=0
for h in range(M,0,-1):
    tmp=0
    for i in range(N):
        if H[i]==h:
            if tmp==0: ans+=1
            tmp=1
            H[i]-=1
        elif H[i]!=h:
            tmp=0
print(ans)

Measured memory_bytes: 3064
#!/usr/bin/env python3
# GRL_5_A: Tree - Diameter of a Tree


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def diameter(graph):
    def dfs(s):
        visited = [False] * graph.v
        weights = [0] * graph.v
        stack = [(s, 0)]
        while stack:
            v, weight = stack.pop()
            if not visited[v]:
                visited[v] = True
                weights[v] = weight
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append((w, weight + e.weight))
        return weights

    v0 = 0
    ws0 = dfs(v0)
    v1 = max((wg, v) for v, wg in enumerate(ws0))[1]
    ws1 = dfs(v1)
    return max(ws1)


def run():
    n = int(input())
    g = Graph(n)

    for _ in range(n-1):
        s, t, w = [int(i) for i in input().split()]
        g.add(WeightedEdge(s, t, w))

    print(diameter(g))


if __name__ == '__main__':
    run()


Measured memory_bytes: 41412
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define gr vector<vpii>
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define GAME_OVER return 0
#define MOD (int)(1E9 + 7)
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vi p(n), q(n);
    for (int& i : p)
        cin >> i;
    for (int& i : q)
        cin >> i;
    vi x(n);
    for (int i = 0; i < n; i++)
        x[i] = i + 1;
    int a = 0, b = 0, i = 0;
    do
    {
        if (x == p)
            a = i;
        if (x == q)
            b = i;
        i++;
    }
    while (next_permutation(all(x)));
    cout << abs(a - b) << endl;
    GAME_OVER;
}

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

int main(void) {

	// TODO: submit前にprintf-debugの削除確認！
	int a, b, c;
	cin >> a >> b >> c;
	int d = max(max(a, b), c);
	
	int ans = a + b + c + d*10;
	if(d == a) ans -= a;
	else if(d == b) ans -= b;
	else ans -= c;
	
	cout << ans;
	return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 200005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll a[maxn],f;

int main()
{
	ll n=read(),m=read(),tmp=1;
	for(int i=1;i<=n;i++)
	{
		a[i]=read(); a[i]/=2;
		tmp=tmp/__gcd(tmp,a[i])*a[i];
		if(tmp>m) {puts("0"); return 0;}
	}
	for(int i=1;i<=n;i++) if((tmp/a[i])%2==0) f=1;
	if(f==1) {puts("0"); return 0;}
	m-=tmp; tmp*=2;
	cout<<1+(m/tmp)<<endl;
	return 0;
}

Measured memory_bytes: 1024
// https://atcoder.jp/contests/abc151/tasks/abc151_d

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

//------------------------------------------------------------------------------
const int V_MAX = 400;
const int INF = 1e6;

int V;
int d[V_MAX][V_MAX];

void warshall_floyd() {
  REP(k, V) REP(i, V) REP(j, V)
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

//------------------------------------------------------------------------------
const int H_MAX = 20;
const int W_MAX = 20;

int H, W;
char S[H_MAX][W_MAX + 1];

int v(int i, int j) { return i * W + j; }

void solve() {
  V = H * W;
  fill(d[0], d[V], INF);
  REP(i, H) REP(j, W) {
    if (S[i][j] == '#') continue;
    if (i > 0 && S[i - 1][j] == '.') d[v(i, j)][v(i - 1, j)] = 1;
    if (i + 1 < H && S[i + 1][j] == '.') d[v(i, j)][v(i + 1, j)] = 1;
    if (j > 0 && S[i][j - 1] == '.') d[v(i, j)][v(i, j - 1)] = 1;
    if (j + 1 < W && S[i][j + 1] == '.') d[v(i, j)][v(i, j + 1)] = 1;
  }
  warshall_floyd();
  // DUMP2D(d, V, V);
  int ans = -1;
  REP(i, V) REP(j, V) {
    if (i != j && d[i][j] < INF) ans = max(ans, d[i][j]);
  }
  printf("%d\n", ans);
}

void input() {
  scanf("%d%d", &H, &W);
  REP(i, H) scanf("%s", S[i]);
}

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


Measured memory_bytes: 896