akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
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; }

const int MOD = 1000000007;
const int INF = 1e9;

const int mod = 1000000007;
const int inf = 1e9;
#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int n;cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int q; cin >> q;
    vector<int> b(n);
    for(int i = 0; i < q; i++) cin >> b[i];

    int cnt = 0;
    for(int i = 0; i < q; i++) {
        if(binary_search(a.begin(), a.end(), b[i])) cnt++;
    } 
    cout << cnt << endl;
}


Measured memory_bytes: 3616
k = int(input())

ans = []
r = [str(i) for i in range(1, 10)]
ans.extend(r)
for _ in range(9):
    rn = []
    for i in r:
        x = int(i[-1])
        if x == 0:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
        elif x == 9:
            rn.append(i+str(x))
            rn.append(i+str(x-1))

        else:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
            rn.append(i+str(x-1))
    ans.extend(rn)
    r = rn[:]

ans = [int(i) for i in ans]
ans.sort()

print(ans[k-1])


Measured memory_bytes: 69596
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    String S = sc.next();
    int r;
    
    if (S.indexOf("RRR") != -1) {
      r = 3;
    }else if (S.indexOf("RR")  != -1) {
      r = 2;
    }else if (S.indexOf('R') != -1) {
      r = 1;
    }else{
      r = 0;
    }
    
    System.out.println(r);
  }
}

Measured memory_bytes: 35576
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const int mod = 1e9 + 7;
int n, dp[N][N];
string str;

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

void dec(int &a, int b) {
	a -= b;
	if (a < 0) {
		a += mod;
	}
}

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

	cin >> n >> str;

	for (int i = 1; i <= n; i++) {
		dp[1][i] = 1;
	}
	for (int len = 2; len <= n; len++) {
		for (int i = 1; i <= len; i++) {
			bool grtr = (str[len - 2] == '<');
			int l = grtr ? i : 1;
			int r = grtr ? len - 1 : i - 1;
			inc(dp[len][i], dp[len - 1][r]);
			dec(dp[len][i], dp[len - 1][l - 1]);
			inc(dp[len][i], dp[len][i - 1]);
		}
	}

	cout << dp[n][n] << '\n';
	return 0;
}


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

  const int MOD = 1000000007;
  const double PI = acos(-1); 

  //long long
  using ll = long long;

  //出力系
  #define print(x) cout << x << endl
  #define yes cout << "Yes" << endl
  #define YES cout << "YES" << endl
  #define no cout << "No" << endl
  #define NO cout << "NO" << endl
  
  // begin() end()
  #define all(x) (x).begin(),(x).end()

  //for
  #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

  //最大公約数（ll）
  ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}

  //素因数分解
  vector<pair<ll, int>>factorize(ll n){
    vector<pair<ll, int>> res;
    for(ll i = 2; i * i <= n; ++i){
      if(n % i) continue;
      res.emplace_back(i, 0);
      while(n % i == 0){
        n /= i;
        res.back().second++;
      }
    }
  if(n != 1) res.emplace_back(n, 1);
  return res;
  }



  //二分探索(最小値を出す問題は疑う)
  bool f(ll K){

  }

  ll binary_search(ll ok, ll ng){
    while(abs(ok - ng) > 1){
      ll mid = (ok + ng) / 2;
      if(f(mid)) ok = mid;
      else ng = mid;
    }
    return ok;
  }



int main(){

  vector<int>a(6);
  REP(i, 3){
    int x, y;
    cin >> x >> y;
    a.at(x)++;
    a.at(y)++;
  }

  int cnt = 0;
  REP(i, 6){
    if(a.at(i) == 2) cnt++;
  }

  if(cnt == 2) YES;
  else NO;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  char ch;
  int counter[27]={0};
  int i;
  int num;
  char abc='a';
  
//  cin.getline(ch,1201,'\n');
//  for(i=0;ch[i]!='\0';i++)
  while(cin >> ch)
  {
    
    if(isupper(ch))
      ch=static_cast<char>(tolower(ch));
    
    num=ch-'a';
    counter[num]++;
  }
  
  for(i=0;i<26;i++)
  {
    cout << abc << " : " << counter[i] <<"\n";
    abc=(int)abc+1;
  }
}

Measured memory_bytes: 1140
#include <iostream>
#include <vector>
#include <set>

using namespace std;

// N:
// v:
// e: in, out
int
main()
{
        int N;
        cin >> N;
        vector<int> ve[N + 1];
        int MAX_J = N - 1;
        for (int i = 1; i <= N; ++i) {
                for (int j = 0; j < MAX_J; ++j) {
                        int opp;
                        cin >> opp;
                        ve[i].push_back(opp);
                }
        }
        int gn = N * (N - 1);
        int g = 0;
        int d = 0;
        // 1回目
        set<int> m;
        for (int i = 1; i <=N; ++i) {
                if (! ve[i].empty()) {
                        if (ve[ve[i][0]][0] == i) {
                                m.insert(i);
                                m.insert(ve[i][0]);
                        }
                }
        }
        if (m.empty()) {
                cout << "-1" << endl;
                return 0;
        }
        for (auto it = m.begin(); it != m.end(); ++it) {
                ve[*it].erase(ve[*it].begin());
                ++g;
        }
        ++d;
        // 残り
        set<int> pm = m;
        m.clear();
        while (true) {
                for (auto it = pm.begin(); it != pm.end(); ++it) {
                        if (! ve[*it].empty()) {
                                if (ve[ve[*it][0]][0] == *it) {
                                        m.insert(*it);
                                        m.insert(ve[*it][0]);
                                }
                        }
                }
                if (m.empty()) {
                        if (gn == g) {
                                cout << d << endl;
                        }
                        else {
                                cout << "-1" << endl;
                        }
                        return 0;
                }
                for (auto it = m.begin(); it != m.end(); ++it) {
                        ve[*it].erase(ve[*it].begin());
                        ++g;
                }
                ++d;
                pm = m;
                m.clear();
        }
        return 0;
}


Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<map>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

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

string s;
string t;

int main()
{
	cin >> s;
	cin >> t;
	int slen = s.length();
	int tlen = t.length();

	int k = 0;
	for (int i = slen-1; i >= tlen-1; i--) {
		int ope = 0;
		for (int j = i; j >= i - tlen + 1; j--) {
			if (s[j] != t[tlen-1-(i-j)] && s[j] != '?') {
				ope++; break;
			}
		}
		if (ope == 0) {
			for (int j = i; j >= i - tlen + 1; j--) {
				s[j] = t[tlen-1-(i-j)];
			}
			k = 1;
			break;
		}
	}
	if (k == 0) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
	for (int i = 0; i < slen; i++) {
		if (s[i] == '?')s[i] = 'a';
	}
	cout << s << endl;
	
	return 0;
}

Measured memory_bytes: 256
class Node():
  def __init__(self):
    self.parent = -1
    self.left = -1
    self.right = -1


n = int(input())
node  = [list(map(int, input().split())) for _ in range(n)] 
result = [Node() for _ in range(n)]
D = [0 for _ in range(n)]
H = [0 for _ in range(n)]


def initiate(li):
  for l in li:
    n = l[0]
    left = l[1]
    right = l[2]
    if left != -1:
      result[left].parent = n
      result[n].left = left
    if right != -1:
      result[right].parent = n
      result[n].right = right

post_list = []
pre_list = []
in_list = []

def preorder(li, root):
  pre_list.append(root)
  if li[root].left != -1:
    preorder(li, li[root].left)
  if li[root].right != -1:
    preorder(li, li[root].right)
  return 

def inorder(li, root):
  if li[root].left != -1:
    inorder(li, li[root].left)
  in_list.append(root)
  if li[root].right != -1:
    inorder(li, li[root].right)
  return 

def postorder(li, root):
  if li[root].left != -1:
    postorder(li, li[root].left)
  if li[root].right != -1:
    postorder(li, li[root].right)
  post_list.append(root)
  return

initiate(node)
root = 0
for i in range(n):
  if result[i].parent == -1:
    root = i 
    break


preorder(result, root)
pre_list = list(map(str, pre_list))
inorder(result, root)
in_list = list(map(str, in_list))
postorder(result, root)
post_list = list(map(str, post_list))

final = []

print("Preorder")
print("", ' '.join(pre_list))
print("Inorder")
print(""," ".join(in_list))
print("Postorder")
print(""," ".join(post_list))




Measured memory_bytes: 5624
import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
S=list(input())
SS=S[0:(len(S)-1)//2]
SSS=S[(len(S)+3)//2:-1]
Sreverse=S[::-1]
if S==S[::-1] and SS==SS[::-1] and SSS==SSS[::-1]:
        print("Yes")
else:
    print("No")



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

const long long INF = 0x3f3f3f3f3f3f3f3f;

struct Line{
	long long k, b;
	Line(){}
	Line(long long _k, long long _b){k = _k, b = _b;}
	long long get(int x){
		return k * x + b;
	}
}t[200010];

long long h[200010];
int tot;

bool cmp(Line a, Line b, Line c){
	double left = 1.0 * (c.b - a.b) / (a.k - c.k);
	double right = 1.0 * (b.b - a.b) / (a.k - b.k);
	return left < right;
}

void add_line(Line a){
	while (tot > 1 && cmp(t[tot - 2], t[tot - 1], a)){
		tot--;
	}
	t[tot++] = a;
}

long long get_min(int x){
	int l = 0, r = tot - 1;
	while (l < r){
		int mid = (l + r) >> 1;
		if (t[mid].get(x) > (mid != tot - 1 ? t[mid + 1].get(x) : INF)) l = mid + 1;
		else r = mid;
	}
	return t[l].get(x);
}

int main(){
	int n; long long C;
	scanf("%d%lld", &n, &C);
	for (int i = 0; i < n; i++){
		scanf("%lld", &h[i]);
	}
	add_line(Line(-2 * h[0], h[0] * h[0]));
	for (int i = 1; i < n - 1; i++){
		long long minj = get_min(h[i]);
		add_line(Line(-2 * h[i], minj + C + 2ll * h[i] * h[i]));
	}
	printf("%lld\n", get_min(h[n - 1]) + C + 1ll * h[n - 1] * h[n - 1]);
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
typedef pair<int,int>   pii;
typedef vector<int>     vi;
typedef long double     ld;
#define MOD         1000000007
#define pb          push_back
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define endl        '\n'
#define PI          3.14159265359d
#define sz(x)       (int)x.size()
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a>c)
    {
        swap(a,c);
        swap(b,d);
    }
    if(c>=b)
        cout<<0;
    else if(d<b)
        cout<<d-c;
    else
        cout<<b-c;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n;
  cin >> n;
  map<string, int> ma;
  rep(i, n) {
    string s;
    cin >> s;
    ma[s]++;
  }

  ll maxi = 0;
  for (auto&& i : ma) {
    cmax(maxi, i.second);
  }

  cerr << endl;
  for (auto&& i : ma) {
    if (i.second == maxi) {
      cout << i.first << endl;
    }
  }
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[55], b[55];
int main() {
  ll n, x;
  cin >> n >> x;
  a[0] = 1;
  for (int i = 1; i <= n; i++) {
    a[i] = a[i - 1] * 2 + 1;
  }
  b[0] = 1;
  for (int i = 1; i <= n; i++) {
    b[i] = b[i - 1] * 2 + 3;
  }
  ll ans = 0;
  while (x > 0) {
    if (x == b[n]) {
      ans += a[n];
      x = 0;
    } else if (x >= b[n] / 2 + 1) {
      ans += a[n - 1] + 1;
      x -= b[n] / 2 + 1;
    } else {
      x--;
    }
    n--;
  }
  cout << ans << endl;
  return 0;
}

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

char a[7][7];
char b[7][7];
int r,c,k;

void dupli()
{
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            b[i][j]=a[i][j];
        }
    }
}

void mark(int x, int y)
{
    for(int i=0; i<r; i++)
    {
        if(x&(1<<i))
        {
            for(int j=0; j<c; j++) b[i][j]='!';
        }
    }
    for(int j=0; j<c; j++)
    {
        if(y&(1<<j))
        {
            for(int i=0; i<r; i++) b[i][j]='!';
        }
    }
}

bool check()
{
    int q=0;
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            if(b[i][j]=='#') q++;
        }
    }
    if (q==k) return true ;
    else return false;
}

int main() 
{
    cin>>r>>c>>k;
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            cin>>a[i][j];
        }
    }
    int answer=0;
    for(int i=0; i<(1<<r); i++)
    {
        for(int j=0; j<(1<<c); j++)
        {
            dupli();
            mark(i,j);
            if(check()) answer++;
        }
    }
    cout<<answer;
    return 0;
}

Measured memory_bytes: 3604
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

using namespace std;

int main()
{
	int N, Q, t, b, c;
	vector<int> map(1e5, 0);
	cin >> N;

	ll sum = 0;
	rep(i, N) {
		cin >> t;
		sum += t;
		map[t] += 1;
	}

	cin >> Q;
	rep(i, Q)
	{
		cin >> b >> c;

		if (map[b] != 0)
		{
			map[c] += map[b];
			sum += (c - b) * map[b];
			map[b] = 0;
		}

		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 3720
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int n = sc.nextInt();
        int[] values = new int[w];
        for (int i = 0; i < w; i++) {
            values[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            String[] ab = str.split(",");
            int a = Integer.parseInt(ab[0]) - 1;
            int b = Integer.parseInt(ab[1]) - 1;
            int tmp = values[a];
            values[a] = values[b];
            values[b] = tmp;
        }
        for(int i = 0; i < w; i++) {
            System.out.println(values[i]);
        }
    }
}


Measured memory_bytes: 25980
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    map<int, ll> memo;
    rep(i, n) {
        memo[a[i]]++;
    }
    ll all = 0;
    for (auto p: memo) {
        ll m = p.second;
        if (m < 2) continue;
        all += m * (m - 1) / 2;
    }
    rep(i, n) {
        ll ans = all - (memo[a[i]] - 1);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 10240
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int A, B;
	cin >> A >> B;
	if (A + B >= 10) cout << "error" << endl;
	else cout << A + B << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i = (a);i < (n);i++)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
  
  	int n,memo = 1,ans = 0;
  	cin >> n;
  	int a[n];
  
  	rep(i,0,n){
      cin >> a[i];
    }
  
  	rep(i,1,n){
      if(a[i-1] == a[i]){
        memo++;
      }
      else{
        ans += memo/2;
        memo = 1;
      }
    }
  
  	ans += memo/2;
  
  	cout << ans << endl;
  	return 0;
}

Measured memory_bytes: 256
#include <iostream>
int nim_num(int x, int k) {
	if (x < k) return 0;
	if (x % k == 0) return x / k;
	return nim_num(x - x / k - 1, k);
}
int main() {
	int n;
	std::cin >> n;
	int res{ 0 };
	{
		int a, k;
		for (auto i = 0; i < n; ++i) {
			std::cin >> a >> k;
			res ^= nim_num(a, k);
		}
	}
	std::cout << (res != 0 ? "Takahashi" : "Aoki") << std::endl;
}

Measured memory_bytes: 888
using System;
using System.Linq;

class E
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var a = read();
		int h = a[0], w = a[1];

		var m = new int[h, w];
		for (int i = 0; i < h; i++)
		{
			var l = read();
			for (int j = 0; j < w; j++)
				m[i, j] = l[j];
		}
		for (int i = 0; i < h; i++)
		{
			var l = read();
			for (int j = 0; j < w; j++)
				m[i, j] -= l[j];
		}

		var M = 80 * (h + w);
		var dp = new bool[h, w, M];
		dp[0, 0, Math.Abs(m[0, 0])] = true;
		for (int k = 0; k < h + w - 2; k++)
		{
			for (int i = 0, j = k; i <= k; i++, j--)
			{
				if (i >= h || j >= w) continue;

				for (int v = 0; v < M; v++)
				{
					if (!dp[i, j, v]) continue;

					if (j + 1 < w)
					{
						dp[i, j + 1, Math.Abs(v + m[i, j + 1])] = true;
						dp[i, j + 1, Math.Abs(v - m[i, j + 1])] = true;
					}
					if (i + 1 < h)
					{
						dp[i + 1, j, Math.Abs(v + m[i + 1, j])] = true;
						dp[i + 1, j, Math.Abs(v - m[i + 1, j])] = true;
					}
				}
			}
		}
		Console.WriteLine(Enumerable.Range(0, M).First(i => dp[h - 1, w - 1, i]));
	}
}


Measured memory_bytes: 93024
using System;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int N = int.Parse(Console.ReadLine());
            Console.WriteLine(N >= 2800 ? "AGC" : (N < 1200 ? "ABC" : "ARC"));
        }
    }
}



Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  if (s[0] == s[1] && s[1] == s[2] || s[1] == s[2] && s[2] == s[3]) { 
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

string replaceAll(string s, const string &f, const string& t) {
    string r;
    for (int p = 0; (p = s.find(f)) != s.npos;) {
        r += s.substr(0, p) + t;
        s = s.substr(p + f.size());
    }
    return r + s;
}

int main(){
    int n;
    int const inf = 1 << 29;
    while (cin >> n && n){
        string a[10], b[10];
        rep(i, n)cin >> a[i] >> b[i];
        queue<pair<int,string>> q;
        string src, dst;
        cin >> src >> dst;
        set<string> dp;
        q.emplace(0, src);
        dp.insert(src);
        int ans = inf;
        while (q.size()){
            auto state = q.front(); q.pop();
            string s = state.second;
            int d = state.first;
            if (s == dst){
                ans = d;
                break;
            }
            auto it = dp.insert(s);
            if (!it.second && d != 0) continue;
            rep(i, n){
                string t = replaceAll(s, a[i], b[i]);
                if (t.size() > dst.size()) continue;
                q.emplace(d + 1, t);
            }
        }
        if (ans == inf)ans = -1;
        cout << ans << endl;
    }
}

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

int main(){
    int A,B,T;
    int sum = 0;
    cin >> A >> B >> T;

    for (int i = 1; i <= 20; i++){
        if (i > T + 0.5){
            break;
        }
        if (i % A == 0){
            sum += B;
        }
    }
    cout << sum << endl;

}


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

int main(void)
{
	int a;
	ll sum=0;
	scanf("%d",&a);
	for(int i=1;i<=a;i++)
	{
		if(i%3!=0&&i%5!=0)
		{
		//	printf("%d\n",i);
			sum+=i;
		}
			
	}
	printf("%lld",sum);
	return 0;
}

Measured memory_bytes: 3792
n,q = map(int,input().split())
s = input()
li = [0]*n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]
for i in range(q):
    l,r = map(int,input().split())
    print(li[r-1]-li[l-1])


Measured memory_bytes: 6060
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();

    int[] A = new int[N];

    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }

    sc.close();
    
    Arrays.sort(A);

    System.out.println(Math.abs(A[0] - A[N-1]));

  }

}

Measured memory_bytes: 23764
using System;
using System.Collections.Generic;
using System.Linq;

namespace AOJ.Volume2
{
    public class CalorieCounting
    {
        private class Confectionery
        {
            public int No { get; set; }
            public int Protein { get; set; }
            public int Lipid { get; set; }
            public int Carbohydrate { get; set; }
            public int Calorie
            {
                get
                {
                    return Protein * 4 + Lipid * 9 + Carbohydrate * 4;
                }
            }
        }

        public static int Main()
        {
            while(true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == 0) { break; }

                var conf = new List<Confectionery>();
                for(int i = 0; i < n; i++)
                {
                    var input = Console.ReadLine().Split(' ');
                    var c = new Confectionery();
                    c.No = int.Parse(input[0]);
                    c.Protein = int.Parse(input[1]);
                    c.Lipid = int.Parse(input[2]);
                    c.Carbohydrate = int.Parse(input[3]);

                    conf.Add(c);
                }

                var rest = Console.ReadLine().Split(' ');
                int r_p = int.Parse(rest[0]);
                int r_l = int.Parse(rest[1]);
                int r_car = int.Parse(rest[2]);
                int r_cal = int.Parse(rest[3]);

                var query = conf.Where(x =>
                    x.Protein <= r_p && x.Lipid <= r_l && x.Carbohydrate <= r_car && x.Calorie <= r_cal);
                if (query.Count() == 0) { Console.WriteLine("NA"); }
                else
                {
                    foreach(var c in query) { Console.WriteLine(c.No); }
                }
            }
            return 0;
        }
    }
}

Measured memory_bytes: 9852
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  sort(all(h));
  reverse(all(h));
  for (int i = 0; i < min(k, n); i++) {
    h[i] = 0;
  }
  cout << accumulate(all(h), 0ll) << endl;
  return 0;
}

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

int main() {
    string abcd;
    cin>>abcd;
    int a[4];
    for (int i=0;i<4;i++)
        a[i]=abcd[i]-'0';
    for (int i=0;i<8;i++) {
        string s;
        int sm=a[0];
        s+=a[0]+'0';
        for (int j=0;j<3;j++) {
            if (i&1<<j) {
                sm+=a[j+1];
                s+="+";
            } else {
                sm-=a[j+1];
                s+='-';
            }
            s+=a[j+1]+'0';
        }
        if (sm==7) {
            s+="=7\n";
            cout<<s;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
n = int(input())
a = Counter(list(map(int, input().split())))

ans = 1

for i, v in a.items():
    if i == 0:
        if v != 1:
            print(0)
            exit()
    elif v != 2:
        print(0)
        exit()
    else:
        ans = ans * 2 % (10 ** 9 + 7)
print(ans)

Measured memory_bytes: 14820
def prime_factor(n):
  ass=[]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:ass.append(i);n//=i
  if n!=1:ass.append(n)
  return ass

n = int(input())
ans = 0
pf = prime_factor(n)

from collections import Counter
c = Counter(pf)
for i in c.keys():
    v = c[i]
    for j in range(1, 10**20):
        if j>v:
            break
        ans += 1
        v -= j
print(ans)

Measured memory_bytes: 9592
#!/usr/bin/env python3
import sys


def solve(K: str):
    T=[]
    for i in range(int(K)):
        T.append('ACL')
    T = "".join(T)
    return print(T)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = next(tokens)  # type: str
    solve(K)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9044
N=int(input())
S=[]
ans=0
for i in range(1,N):
 for j in range(i+1,N+1):
  S.append([i,j])
  ans+=1
if N%2==1:
 for i in range(1,N//2+1):
  S.remove([i,N-i])
  ans-=1
else:
 for i in range(1,N//2+1):
  S.remove([i,N+1-i])
  ans-=1
print(ans)
for j in S:
 print(*j)


Measured memory_bytes: 45296
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define repr(i, n) for(int i = n;i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define MOD 1000000007
 
typedef long long ll;
 

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

    int n,ans = 0,a = 0;
    string s;
    cin >> n >> s;

    rep(i,n){
        if(s[i] == 'I'){
            a++;
        }
        if(s[i] == 'D'){
            a--;
        }
        if(ans < a){
            ans = a;
        }
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
# python 3.8.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
from math import gcd
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def lcm(a,b):return (a*b) // gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

A,B,C,D = imn()

while A >= 0 and C >= 0:
    C -= B
    if C <= 0:
        print('Yes')
        break
    A -= D
    if A <= 0:
        print('No')
        break

Measured memory_bytes: 10636
/*
 * main.c
 *
 *  Created on: 2019/12/29
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;

int A[100000] = {0};
int main()
{
	int H = 0, N = 0, sum = 0, i = 0;
	scanf("%d %d", &H, &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		sum += A[i];
	}

	if (sum >= H) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
    return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

int brute(int x, int cur) {
  int res = 0;
  while (x > 2 * cur) {
    x -= cur;
    res++;
  }
  return res;
}

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

  int n;
  cin >> n;
  ll res = 0;
  int cur = 1;
  while (n-- > 0) {
    int x;
    cin >> x;
    if (cur == 1) {
      res += (x - 1) / cur;
      cur = 2;
    } else {
      if (x == cur) {
        cur++;
        continue;
      }
      int c = max(0, (x - cur - 1) / cur);
//      cout << x << " -> " << c << " " << brute(x, cur) << endl;
      x -= c * cur;
      res += c;
      if (cur < x) {
        res++;
      }
    }
  }
  cout << res;
  return 0;
}

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

using namespace std;
using i64 = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define sqrt(x) sqrt(abs(x))
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define re return
#define prev PREV
#define next NEXT
#define sz(x) ((int)x.size())

template<typename T> T sqr(T a) { re a * a; }
template<typename T> T gcd(T a, T b) { re b ? gcd(b, a % b) : a; }
template<typename T> T sgn(T a) { re a > 0 ? 1 : (a < 0 ? -1 : 0); }
template<typename T> T abs(T a) { re a > 0 ? a : -a; }

const int inf = 2e9;
const ld st = 0.000001;
const ld pi = acos((ld)-1);
const int K = 1000;
const int NMAX = 1000;
#define FILENAME ""   

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
//	freopen("symposium.in", "r", stdin);
//	freopen("symposium.out", "w", stdout);
    string s, s1;
    cin >> s >> s1;
    map <char, int> m;
    for (int i = 0; i < sz(s); i++)
    {
     	m[s[i]]++;
    }
    map <char, int> m1;
    for (int i = 0; i < sz(s1); i++)
    {
     	m1[s1[i]]++;
    }
    vector <int> a, b;
    for (auto it : m) a.pb(it.second);
    for (auto it : m1) b.pb(it.second);
    sort(all(a));
    sort(all(b));
    if (a == b) cout << "Yes";
    else cout << "No";
   	re 0;
}

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

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	for(int i=0;;++i){
		int ans = 1 + (a - 1)*i;
		if(b <= ans){
			cout << i;
			return 0;
		}	
	}
}


Measured memory_bytes: 3636
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=10010;
int n,m,x,y,index_,dfn[maxn],low[maxn],ans,a;
vector<int>G[maxn];
int qwq;
struct Edge{int from,to;}edge[maxn];
bool cmp(const Edge a,const Edge b){if(a.from!=b.from)return a.from<b.from;return a.to<b.to;}
inline void add_edge(int x,int y){edge[ans].from=min(x,y);edge[ans].to=max(x,y);ans++;}
void dfs(int cur,int fa)
{
    int child;
    dfn[cur]=++index_;
    low[cur]=dfn[cur];
    bool vis=false; 
    for(int i=0;i<G[cur].size();i++)
    {
        child=G[cur][i];
        if(dfn[child])
        {
            if(child==fa&&!vis)vis=true;
            else low[cur]=min(low[cur],dfn[child]);
        }
        if(!dfn[child])
        {
            dfs(child,cur);
            if(dfn[cur]<low[child])add_edge(cur,child);
            low[cur]=min(low[cur],low[child]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,i);
    sort(edge,edge+ans,cmp);
    for(int i=0;i<ans;i++) qwq++;
printf("%d\n",qwq);
    return 0;
}

Measured memory_bytes: 512
def prime_factorization(n):
    for i in range(2, n + 1):
        num = int(i ** 0.5)
        for prime in range(2, num + 2):
            if i % prime == 0:
                cnt = 0
                while True:
                    if i % prime != 0: break
                    cnt += 1
                    i = i // prime
                if rec.get(prime):
                    rec[prime] += cnt
                else:
                    rec[prime] = cnt

        if i != 1:
            if rec.get(i):
                rec[i] += 1
            else:
                rec[i] = 1

n = int(input())
rec = dict()
prime_factorization(n)
dic = {2:0, 4:0, 14:0, 24:0, 74:0}
cnt = 0
for key, val in rec.items():
    if val >= 2:dic[2] += 1
    if val >= 4:dic[4] += 1
    if val >= 14:dic[14] += 1
    if val >= 24:dic[24] += 1
    if val >= 74:dic[74] += 1

for i in [74, 24, 14, 4]:
    temp = dic.get(i)
    if i == 74:cnt += temp
    elif i == 24:cnt += temp * (dic[2] - 1)
    elif i == 14:cnt += temp * (dic[4] - 1)
    else:cnt += (dic[2] - 2) * (temp - 1) * temp // 2
print(cnt)

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

struct Edge {
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;

ll C[100001];

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

  int N; cin >> N;

  Graph G(N + 1);
  rep(_, N - 1) {
    int from, to, weight;
    cin >> from >> to >> weight;
    G[from].push_back(Edge(to, weight));
    G[to].push_back(Edge(from, weight));
  }

  int Q,K; cin >> Q >> K;
  queue<int> QU;
  QU.push(K);

  while(!QU.empty()) {
    int cur = QU.front(); QU.pop();
    rep(i, G[cur].size()) {
      Edge next = G[cur][i];  
      if(C[next.to] == 0) {
        QU.push(next.to);
        C[next.to] = C[cur] + next.weight;
      }
    }
  }

  rep(i, Q) {
    int from, to;
    cin >> from >> to;

    cout << C[from] + C[to] << endl;
  }

  return 0;
}


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


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


L = [0 for i in range(N)]
R = [0 for i in range(N)]
l = A[0]
r = A[-1]
for i in range(N):
    l = gcd(l, A[i])
    r = gcd(r, A[-(i+1)])
    L[i] = l
    R[i] = r

ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, R[N-2])
    elif i == N-1:
        ans = max(ans, L[i-1])
    else:
        ans = max(ans, gcd(L[i-1], R[N-2-i]))

print(ans)

Measured memory_bytes: 67436
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

bool reach[MAX_N];
vector<int> edge[MAX_N];

void dfs(int now){
    if(reach[now]) return;
    reach[now]=true;
    rep(i,edge[now].size()) dfs(edge[now][i]);
}

int main(void){
    int N;
    cin >> N;
    int A[N],B[N];
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    int C[N+1]={};
    int D[N+1]={};
    rep(i,N) C[0]=C[0]^A[i],D[0]=D[0]^B[i];
    rep(i,N) C[i+1]=A[i],D[i+1]=B[i];
    int E[N+1],F[N+1];
    rep(i,N+1) E[i]=C[i],F[i]=D[i];
    sort(C,C+N+1);
    sort(D,D+N+1);
    bool chk=true;
    rep(i,N+1) if(C[i]!=D[i]) chk=false;
    if(!chk){
        cout << -1 << endl;
        return 0;
    }
    sort(A,A+N);
    sort(B,B+N);
    bool m1=false;
    int m2=0;
    int base=N;
    bool m4=false;
    rep(i,N) if(A[i]!=B[i]) m1=true;
    if(E[0]!=F[0]){
        m4=true;
        rep(i,N) if(E[i+1]!=F[i+1] && F[i+1]==E[0]){
            swap(E[i+1],E[0]);
            break;
        }
    }
    map<int,int> place;
    pint p[N+1];
    rep(i,N+1) p[i].fi=E[i],p[i].se=i;
    sort(p,p+N+1);
    rep(i,N+1) if(E[i]!=F[i]) place[E[i]]=i;
    rep(i,N+1){
        if(E[i]==F[i]) base--;
        else{
            edge[place[E[i]]].push_back(place[F[i]]);
            edge[place[F[i]]].push_back(place[E[i]]);
        }
        if(i==0 && E[i]==F[i]) base++;
    }
    rep(i,N) if(p[i].fi==p[i+1].fi){
        edge[p[i].se].push_back(p[i+1].se);
        edge[p[i+1].se].push_back(p[i].se);
    }
    int ans=base;
    rep(i,N+1){
        if(!reach[i]) if(E[i]!=F[i]) dfs(i),ans++;
    }
    rep(i,N) if(E[i+1]!=F[i+1] && F[i+1]==E[0]){
        ans--;
        break;
    }
    if(m4) ans++;
    cout << ans << endl;
}


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define tr(ds, it) for(auto it=ds.begin(); it!=ds.end(); it++)
#define rtr(ds, it) for(auto it=ds.rbegin(); it!=ds.rend(); it--)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef priority_queue <int> pq;
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define graph vector<vi>

const ll mod = 1000000007;
ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
         if(n&1) ans=(ans*x)%mod;
         x=(x*x)%mod;
         n/=2;
     }
     return ans;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  
    int T=1;
    //cin >> T;
    while(T--){
        ll x;
        cin>>x;
        ll a=0;
        a=1000*(x/500);
        x%=500;
        a+=5*(x/5);
        cout<<a<<el;
    }

    return 0;
}

Measured memory_bytes: 256
import collections
from pprint import pprint as pp

a = int(input())
b = int(input())
c = int(input())
x = int(input())

result = 0

for x500 in range(a+1):
  now_500 = 500 * x500
  if now_500 > x:
    break
  for x100 in range(b+1):
    now_100 = 100 * x100 + now_500
    if now_100 > x:
      break
    rem = (x - now_100) / 50
    if rem <= c:
      result += 1
print(result)


Measured memory_bytes: 3700
#pragma GCC optimize("O3")
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<string>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define FOR(i,l,r) for(int i = l ; i <= r ;++i )
#define ALL(T)  T.begin(),T.end()
#define lson(i)     i<<1
#define rson(i)     (i<<1|1)
#define ll long long 
#define pu push
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define is insert
#define se second
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define debug(x) cout << "[" << #x << ": " << (x) << "]" << endl
#define endl "\n"
#define in inline
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5+10;
const int INF = 1<<30;
int a[N];
int dp[N];
int n;
int main(){
    cin >> n;
    FOR(i,1,n)  cin >> a[i];
    for(int i=n;i>=1;--i){
        if(a[i]>=a[i+1])    dp[i] = dp[i+1]+1;
        else dp[i] = 1;
    }
    cout << *max_element(dp+1,dp+1+n)-1 << endl;
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int, input().split()))

ans = 0
r = -1
xor_n = 0
sum_n = 0
for l in range(n):
    while True:
        r += 1

        if r < n:
            nr = a[r]
            xor_n ^= nr
            sum_n += nr
            ok = xor_n == sum_n
        if r >= n or not ok:
            ans += (r - 1) - l + 1
            sum_n -= nr
            sum_n -= a[l]
            xor_n ^= nr
            xor_n ^= a[l]
            r -= 1
            break
print(ans)

Measured memory_bytes: 24584
#include<math.h>
#include<time.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int dice[10];
void roll(char onecommand)
{
	char t=dice[1];
	if(onecommand=='W')
	{
		dice[1]=dice[3];
		dice[3]=dice[6];
		dice[6]=dice[4];
		dice[4]=t;
	}
	if(onecommand=='S')
	{
		dice[1]=dice[5];
		dice[5]=dice[6];
		dice[6]=dice[2];
		dice[2]=t;
	}
	if(onecommand=='E')
	{
		dice[1]=dice[4];
		dice[4]=dice[6];
		dice[6]=dice[3];
		dice[3]=t;
	}
	if(onecommand=='N')
	{
		dice[1]=dice[2];
		dice[2]=dice[6];
		dice[6]=dice[5];
		dice[5]=t;
	}
	return;
}
int main()
{
	int i,len;
	char command[110];
	scanf("%d %d %d %d %d %d",&dice[1],&dice[2],&dice[3],&dice[4],&dice[5],&dice[6]);
	scanf("%s",command);
	len=strlen(command);
	for(i=0;i<=len-1;i++)
		roll(command[i]);
	printf("%d\n",dice[1]);
	return 0;
}


Measured memory_bytes: 2120
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	vector<ll> a(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	ll res = 1;
	ll m = a[0];
	for (ll i = 1; i < n; i++)
	{
		if (m > a[i])
		{
			res++;
			m = a[i];
		}
	}

	println(res);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i], a[i]--;

    vector<int> ql(q), qr(q), qi(q);
    rep(i, q) cin >> ql[i] >> qr[i], ql[i]--;
    iota(qi.begin(), qi.end(), 0);

    int width = n / sqrt(q);
    sort(qi.begin(), qi.end(), [&](int i, int j) {
        if (ql[i] / width != ql[j] / width) return ql[i] < ql[j];
        else {
            int k = ql[i] / width;
            if (k % 2 == 0) return qr[i] < qr[j];
            else return qr[i] > qr[j];
        }
    });

    vector<int> cnt(n), ans(q);
    int sum = 0;
    int l = 0, r = 0;

    auto add = [&](int i) { if (cnt[a[i]]++ == 0) sum++;};
    auto del = [&](int i) { if (--cnt[a[i]] == 0) --sum;};
    
    for (int i : qi) {
        while (ql[i] < l) add(--l);
        while (r < qr[i]) add(r++);
        while (l < ql[i]) del(l++);
        while (qr[i] < r) del(--r);
        ans[i] = sum;
    }
    
    rep(i, q) cout << ans[i] << endl;
}


Measured memory_bytes: 15484
def calc_hash(s, base, h):
    res = 0
    multi = 1
    for e in s:
        res = (res+ord(e)*multi) % h
        multi *= base
    return res


T = input()
P = input()

base = 100
h = 10**9+7
base_inv = pow(base, h-2, h)
base_m = pow(base, len(P), h)
hash = calc_hash(P, base, h)
curr_hash = calc_hash(T[0:len(P)], base, h)
ans = []
if(hash == curr_hash):
    ans.append(0)
for i in range(1, len(T)-len(P)+1):
    curr_hash = (
        (curr_hash-ord(T[i-1])+ord(T[i+len(P)-1])*base_m)*base_inv) % h
    if(curr_hash == hash):
        ans.append(i)
for e in ans:
    print(e)



Measured memory_bytes: 47916