akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef long double ld;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};





int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n,m;
    cin>>n;
    int cnt[4] = {};
    
    rep(i,n){
        string s;
        cin>>s;

        if(s == "AC")cnt[0]++;
        if(s == "WA")cnt[1]++;
        if(s == "TLE")cnt[2]++;
        if(s == "RE")cnt[3]++;
    }


    cout<<"AC x "<<cnt[0]<<endl;
    cout<<"WA x "<<cnt[1]<<endl;
    cout<<"TLE x "<<cnt[2]<<endl;
    cout<<"RE x "<<cnt[3]<<endl;

    //cout <<fixed<<setprecision(16)<< << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;

    return 0;
}


Measured memory_bytes: 3624
S = input()

string_num = len(S) // 2

is_true = True
if len(S) % 2 != 0:
    is_true = False

elif S.count('h') != string_num or S.count('i') != string_num:
    is_true = False

else:
    for i in range(0, len(S) - 1, 2):
        if S[i:i + 2] != 'hi':
            is_true = False

if is_true:
    print('Yes')
else:
    print('No')


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

int main(){
    // 制約見て！！！デカかったらlong longにすること！
    int N;
    cin >> N;
    int a;
    int max = -1,min = -1;
    rep(i,N){
        cin >> a;
        if (max == -1 || a > max)
            max = a;
        if (min == -1 || a < min)
            min = a;
    }

    cout<< max - min <<endl;
}

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

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

    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '7'){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3652
N, P = map(int, input().split())
A = [int(i) for i in input().split()]

o, e = 0, 0
for i in range(N) :
  if A[i] % 2 == 0 :
    e += 1
  else :
    o += 1

ret = pow(2, e) * max(1, pow(2, o - 1))

if P == 0 :
  print(ret)
else :
  print(pow(2, N) - ret)

Measured memory_bytes: 38256
N = int(input())
S = input()
now = 0
right = 0
left = 0
add_left = 0
while now < N:
    if S[now] == '(':
        left += 1
    else:
        if left:
            left -= 1
        else:
            add_left += 1
    now += 1
for _ in range(add_left):
    print('(', end='')
print(S, end='')
for _ in range(left):
    print(')', end='')



Measured memory_bytes: 9188
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    int N, M;
    cin >> N >> M;

    string s;
    cin >> s;


    vector<vector<int>> edge(N);
    vector<int> A(N, false);
    vector<int> B(N, false);
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
        s[a] == 'A' ? A[b]++ : B[b]++;
        s[b] == 'A' ? A[a]++ : B[a]++;
    }

    vector<bool> ok(N);
    queue<int> d;
    REP(i, N) {
        if (A[i] == 0 || B[i] == 0) {
            d.push(i);
            ok[i] = false;
        }
        else {
            ok[i] = true;
        }
    }

    while (!d.empty()) {
        int cur = d.front(); d.pop();

        REP(i, edge[cur].size()) {
            int t = edge[cur][i];
            if (!ok[t]) continue;

            s[cur] == 'A' ? A[t]-- : B[t]--;

            if (A[t] == 0 || B[t] == 0) {
                d.push(t);
                ok[t] = false;
            }
        }
    }

    REP(i, N) {
        if (!ok[i]) continue;

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

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


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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var A = new int[N];
            for (int i = 0; i < N; i++) A[i] = ReadInt();
            var minL = new List<int>();
            var cnt = 0;
            minL.Add(A[N - 1]);
            cnt++;
            for (int i = N - 2; i >= 0; i--)
            {
                var idx = UpperBound(minL, A[i]);
                if (idx == minL.Count())
                {
                    minL.Add(A[i]);
                    cnt++;
                }
                else
                {
                    minL[idx] = A[i];
                }
            }

            Console.WriteLine(cnt);
            Console.ReadLine();
        }

        static int UpperBound(List<int> arr, int val)
        {
            val++;
            if (arr[0] >= val) return 0;
            if (arr[arr.Count() - 1] < val) return arr.Count();

            var low = 0;
            var high = arr.Count() - 1;

            while (low + 1 < high)
            {
                var mid = (low + high) / 2;
                if (arr[mid] >= val) high = mid;
                else low = mid;
            }

            return high;
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 15964
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    static boolean isPalindrome(String s) {
        for (int i = 0; i <= (s.length() - 1)/ 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line;
        int result = 0;
        while ((line = br.readLine()) != null) {
            if (isPalindrome(line))
                result++;
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 24184
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int D;
    static int r;
    static int result;
    public static void main(final String[] args) throws NumberFormatException, IOException {

        String[] input = br.readLine().split(" ");
        r = Integer.parseInt(input[0]);
        D = Integer.parseInt(input[1]);
        int xi = Integer.parseInt(input[2]);

        for (int i = 1; i <=10; i++){
            xi = algaeDev(xi);
            System.out.println(xi);

        }


    
    }

    public static int algaeDev(int xi){
        return r * xi - D;
    }

}

Measured memory_bytes: 32640
#include <stdio.h>

int main() {
  int a;
  int b;

  scanf("%d %d",&a,&b);

  int r=a%b;
  while(r!=0) {

    a=b;
    b=r;
    r=a%b;
  }
  printf("%d\n",b);

  return 0;
}



Measured memory_bytes: 2084
#include<bits/stdc++.h>                                                   //---------------------------------------------------------------
                                                                    
# define ll long long   
# define ld long double                                               
# define mod 1000000007                                                   
# define MAX 100005
# define pi 3.141592653589793238                                                                                  //shortcut keys
                                                                                
# define pb push_back                                                                     
# define mp make_pair 
# define all(x) x.begin(),x.end()                                                      
                                                                  
# define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);        //---------------------------------------------------------------                                       
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int a[n]={0};
	for(int i=0;i<k;i++){
		int x;
		cin>>x;
		for(int i=0;i<x;i++){
			int y;
			cin>>y;
			y--;
			a[y]=1;
		}
		
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(a[i]==0)ans++;
	}
	cout<<ans<<"\n";
	return 0;

	
}

Measured memory_bytes: 3640
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>

using namespace std;

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

using ll = long long;
using P = pair<int, int>;

const long long MOD = 1e9+7;

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; }

template<class T>
istream& operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    if (h < w) swap(h, w);
    cout << (n + h - 1) / h << endl;
}

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

int main(void) {

  char s[100001];
  scanf("%s", s);
  int length = strlen(s);
  int a = 0, b = 0, c = 0;
  for (int i = 0; i < length; i++) {
    if (s[i] == 'a') {
      a++;
    } else if (s[i] == 'b') {
      b++;
    } else {
      c++;
    }
  }
  int min = a;
  if (b < min) {
    min = b;
  }
  if (c < min) {
    min = c;
  }
  if (a-min < 2 && b-min < 2 && c-min < 2) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << endl;
#else
	#define DBG(X)
	#define endl '\n'
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const ll mod = 1e9 + 7;
const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }

const int MAX_N = (int)1e5 + 77;

int h[MAX_N], n;
bool dp0[MAX_N], dp1[MAX_N];

void solve()
{
	h[0] = -13;
	dp0[0] = true;
	dp1[0] = true;

	cin >> n;

	for(int i = 1; i <= n; ++i)
	{
		cin >> h[i];

		dp0[i] = (h[i] >= h[i - 1] && dp0[i - 1]) || (h[i] >= h[i - 1] - 1 && dp1[i - 1]);
		dp1[i] = (h[i] - 1 >= h[i - 1] && dp0[i - 1]) || (h[i] - 1 >= h[i - 1] - 1 && dp1[i - 1]);
	}

	cout << (dp0[n] || dp1[n] ? "Yes" : "No") << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
using namespace std;
#define N 200005
#define lc (o<<1)
#define rc (o<<1|1)
int n,m,b[N],sum,mi[N<<2],tg[N<<2];
struct node{ int l,r; }a[N];
const bool cmp(const node &x,const node &y){ return x.l<y.l; }
void down(int o){
	if (!tg[o]) return;
	mi[lc]+=tg[o]; mi[rc]+=tg[o]; tg[o]=0;
}
void up(int o){ mi[o]=min(mi[lc],mi[rc]); }
int qrymin(int o,int l,int r,int x,int y){
	if (x<=l && r<=y) return mi[o];
	down(o); int mid=l+r>>1,ret=inf;
	if (x<=mid) ret=min(ret,qrymin(lc,l,mid,x,y));
	if (y>mid) ret=min(ret,qrymin(rc,mid+1,r,x,y));
	return ret;
}
void modify(int o,int l,int r,int x,int val){
	if (l==r){ mi[o]=val; return; }
	down(o); int mid=l+r>>1;
	if (x<=mid) modify(lc,l,mid,x,val);
	else modify(rc,mid+1,r,x,val); up(o);
}
void add(int o,int l,int r,int x,int y,int val){
	if (x<=l && r<=y){ tg[o]+=val,mi[o]+=val; return; }
	down(o); int mid=l+r>>1;
	if (x<=mid) add(lc,l,mid,x,y,val);
	if (y>mid) add(rc,mid+1,r,x,y,val); up(o);
}
int main(){
	scanf("%d",&n);
	rep (i,1,n) scanf("%d",&b[i]),sum+=!b[i];
	scanf("%d",&m);
	rep (i,1,m) scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+1+m,cmp); int po=1;
	memset(mi,127,sizeof(mi)); modify(1,0,n,0,0);
	rep (i,1,n){
		//f[i][j]表示前i个数已经确定，最后一个1在第j位，最小的(0,1)-(0,0)。一位一位确定。
		while (po<=m && a[po].l<=i){
			modify(1,0,n,a[po].r,qrymin(1,0,n,0,a[po].r));//f[i][r]=min{f[i-1][k]}(k<=r);
			po++;
		}
		add(1,0,n,0,i-1,b[i]?1:-1);
	}
	printf("%d\n",mi[1]+sum);
	return 0;
}
/*
15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13
*/

Measured memory_bytes: 8832
import sys
from bisect import bisect_right


def meet_in_the_middle(a: list, limit: int) -> tuple:
    first_v, first_w, second_v, second_w = [], [], [], []
    for items, v_append, w_append in (
            (a[:len(a)//2], first_v.append, first_w.append),
            (a[len(a)//2:], second_v.append, second_w.append)
    ):
        enumerated = [(0, 0)]
        for v, w in items:
            enumerated += [(w+_w, v+_v) for _w, _v in enumerated]

        enumerated.sort()
        enumerated = enumerated[:bisect_right(enumerated, (limit, float("inf")))] + [(limit+1, 0)]
        max_v = -1
        for (cw, cv), (nw, nv) in zip(enumerated, enumerated[1:]):
            if cw < nw and max_v < cv:
                v_append(cv)
                w_append(cw)
                max_v = cv

    return (first_v, first_w), (second_v, second_w)


N, W = map(int, input().split())
a = [list(map(int, l.split())) for l in sys.stdin]

(first_v, first_w), (second_v, second_w) = meet_in_the_middle(a, W)
ans = 0
for v, w in zip(first_v, first_w):
    i = bisect_right(second_w, W-w)-1
    new_v = v + second_v[i]
    if ans < new_v:
        ans = new_v
print(ans)


Measured memory_bytes: 183800
# -*- coding: utf-8 -*-

n = int(raw_input())
d, x = map(int, raw_input().split())
ans = x
val = []
for i in range(n):
    val.append(int(raw_input()))

for i in val:
    for j in range(d):
        if (i*j + 1) <= d:
            ans = ans + 1
        else :
            continue

print ans

Measured memory_bytes: 2568
import math
def main():
  n, a, b = map(int, input().split())
  total = 0
  
  # if n <= a + b:
  #   print(int(n - b))
  # else:
  x = math.floor(n / (a+b))
  total = a * x
  y = n % (a+b)
  if y >= a:
    total += a
  else:
    total += y
      
      
  print(total)
  
  
main()


Measured memory_bytes: 9148
n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 18] * (n+1)
dp[1] = 0
for i,v in enumerate(h,1):
  for j in range(i+1,min(n+1,i+k+1)):
    dp[j] = min(dp[j],dp[i]+abs(v-h[j-1]))
print(dp[n])


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

int main() {
  int a, b;
  cin >> a >> b;
  int n;
  if (b / 100 >= 1) n = a * 1000 + b;
  else if (b / 10 >= 1) n = a * 100 + b;
  else n = a * 10 + b;
  bool ans = false;
  for (int i = 1; i <= n; i++) {
    if (i * i == n) {
      ans = true;
      break;
    }
  }
  if (ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int arr[n];
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  int dp[n];
  dp[0]=0;
  dp[1]=abs(arr[1]-arr[0]);
  for(int i=2;i<n;i++)
  {
      dp[i]=INT_MAX;
    for(int j=1;j<=k;j++){
    if(i-j>=0)
    dp[i]=min(dp[i-j]+abs(arr[i]-arr[i-j]),dp[i]);
    else 
    break;
      }
  }
  cout<<dp[n-1]<<"\n";
}

Measured memory_bytes: 4376
A=[0]*5
B=0
A[0]=int(input())
A[1]=int(input())
A[2]=int(input())
A[3]=int(input())
A[4]=int(input())
count=0
for i in range(0,5):
    if A[i]%10==0:
        count+=A[i]
    else:
        if B==0:
            B=A[i]
        elif B%10>=A[i]%10:
            count+=((B+10)-(B%10))
            B=A[i]
        else:
            count+=((A[i]+10)-(A[i]%10))
print(count+B)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(helper(n));
    }

    static int helper(int n) {
        int res = 0;
        if (n < 10) {
            res = n;
        } else if (n < 100) {
            res = 9;
        } else if (n < 1000) {
            res = n - 90;
        } else if (n < 10000) {
            res = 909;
        } else if (n < 100000) {
            res = n + 910 - 10000;
        } else if (n == 100000) {
            res = 90909;
        }
        return res;
    }
}

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

int main(){
       map<string,int> m;

    int t; cin >> t;
    int max_freq = -1;
    while(t--){
        string s;
        cin >> s;
        m[s]++;
        max_freq = max(max_freq, m[s]);
    }
    vector<string> ans;
    map<string, int>::iterator it;
    for ( it = m.begin(); it != m.end(); it++)
    {
        if(it->second == max_freq) ans.push_back(it->first);
    }
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++) cout << ans[i] << endl;


    


}



Measured memory_bytes: 26868
def chess(h,w):
    o = ""
    for i in range(h):
        if i%2:
            if w%2: o+= ".#"*(w/2)+".\n"
            else: o+= ".#"*(w/2)+"\n"
        else:
            if w%2: o+= "#."*(w/2)+"#\n"
            else: o+= "#."*(w/2)+"\n"
    print o

while 1:
    h,w=map(int,raw_input().split())
    if h==w==0:break
    chess(h,w)

Measured memory_bytes: 4228
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> color(n, 0);
    for(int& val: color)
        cin >> val;
    int idx = 0;
    vector<vector<int>> ans(h, vector<int>(w, 0));
    for(int i = 0; i < h; i++) {
        if (i % 2 == 0) {
            for(int j = 0; j < w; j++) {
                while (color[idx] <= 0)
                    idx++;
                ans[i][j] = idx+1;
                color[idx]--;
            }
        } else {
            for(int j = w-1; j >= 0; j--) {
                while (color[idx] <= 0)
                    idx++;
                ans[i][j] = idx+1;
                color[idx]--;
            }
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
    return 0;
}




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

typedef long long ll;



int main()
{
	

    ll n,i;
    cin>>n;
    ll arr[n];
    map <ll,ll> freq;
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
        freq[arr[i]]++;
    }
    ll totalsum = 0;
    for(auto a:freq)
    {
        //cout<<a.second<<" ";
        totalsum += (a.second*(a.second-1))/2;
    }
    ll res[n];
    //cout<<totalsum<<endl;
    for(i=0;i<n;i++)
    {
        ll extra = freq[arr[i]];
        res[i] = totalsum - (extra-1);

    }
    for(i=0;i<n;i++)
        cout<<res[i]<<endl;

    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin() x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin() x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a[5], n, mini=LONG_LONG_MAX;
	cin >> n;
	rep(i, 5){
		cin >> a[i];
		mini = min(mini, a[i]);
	}
	cout << 4+(n+mini-1)/mini << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    char S[110];
    cin >> N;
    rep(i,0,N){
        cin >> S[i];
        if(S[i] == 'Y'){
            print("Four");
            return 0;
        }
    }
    print("Three");

}

Measured memory_bytes: 256
/**

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*/

#include <bits/stdc++.h>
#define ll long long
#define mp(a,b) make_pair((a),(b))
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mapl map<pll,ll>
#define pi acos(-1)
#define gcd2(a,b) __gcd((a),(b))
#define eps 1e-6
#define meme memset(x,0,sizeof(x))
#define ft first
#define sn second
#define bn0(z) __builtin_clz(z)
#define nd0(z) __builtin_ctz(z)
#define no1(z) __builtin_popcount(z)
using namespace std;

const int N = 200043;
const int MOD = 998244353;
int fact[N];
long long Binexpo(long long a,long long b){
    if(b==0)
        return 1;
    long long res=Binexpo(a,b/2);
    if(b%2){return res*res*a;}
    else{return res*res;}
}

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int inv(int x)
{
    return Binexpo(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}
void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

int C(int n, int k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

long long gcd(long long a,long long b){
    return b?gcd(b,a%b):a;
}

long long primechk[10000];

void preprocess(long long N){
    long long i,j;
    for(i=2;i<=N;i++){
        primechk[i]=1;
    }
    for(i=2;i<=N;i++){
        if(primechk[i]==1){
            for(j=2;i*j<=N;j++){primechk[i*j]=0;}
        }
    }
}

bool isPrime(int n) {
 
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
long long Pwr(long long a,long long b,long long m){
    a%=m;
    long long res=1;
    while(b>0){
        if(b%2){res=res*a%m;}
        a=a*a%m;
        b>>=1;
    }
    return res;
}
int main()
{   long long a,b,c,d,e,f,g=500,h,i,j,k,x,y,z,sum=0,cnt=0,n,l,r,hi,lo,testc,val=1;
    //cin>>testc;
    testc=1;
    long long mx=0;
    while(testc--){
        cin>>n>>k;
        int arr[n];
        for(i=0;i<n;i++){cin>>arr[i];}
        sort(arr,arr+n);
        for(i=0;i<k;i++){sum+=arr[i];}
        cout<<sum;
        
    }
    return 0;
}


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

*/


int main(){
  ll N,oo=1e7,ans=0; cin>>N;
  vector<ll> V(oo+1,1);
  for(ll i=2; i<=oo; i++){
    ll j=i;
    while(j<=oo){
      V[j]++;
      j+=i;
    }
  }
  for(ll i=1; i<=N; i++) ans+=V[i]*i;
  cout<<ans<<endl;
}

Measured memory_bytes: 81396
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,R=map(int,input().split())
    print(R+100*max(0,(10-N)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for (int i=0,_n=(int)(n); i < _n; i++)
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> bool chmin(T &a, T b) { return a > b ? (a = b, true) : false; }
 
typedef long long ll;

int a[512][512];
int b[512][512];

int main2() {
  int H, W;
  cin >> H >> W;
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  vector<string> vs;
  REP(i, H) {
    string s; cin >> s;
    vs.push_back(s);
  }
  REP(i, W) a[0][i] = 1;
  REP(i, W) b[H-1][i] = 1;
  REP(i, H) REP(j, W) {
    if (i < H - 1 && j % 2 == 0) a[i][j] = 1;
    if (i > 0 && j % 2 == 1) b[i][j] = 1;
  }

  REP(i, H) REP(j, W) if (vs[i][j] == '#') {
    a[i][j] = 1;
    b[i][j] = 1;
  }

  REP(i, H) {
    REP(j, W) cout << (a[i][j] == 1 ? "#" : ".");
    cout << endl;
  }
  cout << endl;
  REP(i, H) {
    REP(j, W) cout << (b[i][j] == 1 ? "#" : ".");
    cout << endl;
  }
  cout << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}

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

int main()
{
	int64_t x, y, ans =1;
	cin >> x >> y;
	while(1)
	{
		if( x*2 <= y)
			ans++;
		else
			break;
		x*=2;

	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 384
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
    
		// 出力
		System.out.println(a < 6 ? 0 : a < 13 ? b / 2 : b);
	}
}

Measured memory_bytes: 21844
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	Scanner sc = new Scanner(System.in);

	int INF = 1 << 28;
	double EPS = 1e-9;

	int n,m,p,a,b;
	int[] t;
	LinkedList<E>[] es;
	
	@SuppressWarnings("unchecked")
	void run() {
		for(;;){
			n=sc.nextInt(); // ツ馬
			m=sc.nextInt(); // ツ都ツ市
			p=sc.nextInt(); // ツ督ケツ路
			a=sc.nextInt();
			b=sc.nextInt();
			if((n|m|p|a|b)==0){
				break;
			}
			a--;
			b--;
			es=new LinkedList[m];
			for(int i=0;i<m;i++){
				es[i]=new LinkedList<E>();
			}
			t=new int[n];
			for(int i=0;i<n;i++){
				t[i]=sc.nextInt();
			}
			for(int i=0;i<p;i++){
				int x=sc.nextInt()-1;
				int y=sc.nextInt()-1;
				int z=sc.nextInt();
				es[x].add(new E(y,z));
				es[y].add(new E(x,z));
			}
			solve();
		}
	}
	
	void solve() {
		double[][] d=new double[m][1<<n];
		for(int i=0;i<m;i++){
			fill(d[i],INF);
		}
		d[a][(1<<n)-1]=0;
		PriorityQueue<P> que=new PriorityQueue<P>();
		que.offer(new P(a,(1<<n)-1,0));
		for(;!que.isEmpty();){
			P p=que.poll();
//			debug(p.v,Integer.toBinaryString(p.s),p.d);
			if(p.d>d[p.v][p.s]+EPS){
				continue;
			}
			for(E e:es[p.v]){
				for(int i=0;i<n;i++){
					if((p.s>>i&1)==1){
						P q=new P(e.to,p.s&~(1<<i),p.d+(double)e.cost/t[i]);
						if(q.d<d[q.v][q.s]){
							d[q.v][q.s]=q.d;
							que.offer(q);
						}
					}
				}
			}
		}
		double min=INF;
		for(int i=0;i<1<<n;i++){
			min=min(min,d[b][i]);
		}
		if(min==INF){
			println("Impossible");
		}else{
			println(min+"");
		}
	}
	
	class P implements Comparable<P>{
		int v,s;
		double d;
		P(int v,int s,double d){
			this.v=v;
			this.s=s;
			this.d=d;
		}
		@Override
		public int compareTo(P p) {
			if(d+EPS<p.d){
				return -1;
			}else if(d>p.d+EPS){
				return 1;
			}else{
				return 0;
			}
		}
	}
	
	class E{
		int to,cost;
		E(int to,int cost){
			this.to=to;
			this.cost=cost;
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s) {
		System.out.print(s);
	}

	void println(String s) {
		System.out.println(s);
	}

	public static void main(String[] args) {
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 0
n, l = map(int, input().split())
taste = [i for i in range(l,l+n)]
abs_taste = [abs(t) for t in taste]
min_taste = min(abs_taste)
if min_taste == 0:
	print(sum(taste))
elif min_taste in taste:
	print(sum(taste) - min_taste)
else:
	print(sum(taste) + min_taste)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
const ll mod = 1000000007;
const ll INF = 1e+14;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define _GLIBCXX_DEBUG

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll x=a*c;
    ll y=b*d;
    ll w=a*d;
    ll z=b*c;
    ll ans=max(x,y);
    ans=max(ans,w);
    ans=max(ans,z);
    cout<<ans<<endl;
}

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

int main(void)
{   
    long double pi = M_PI;
    long double A,B;
    long double H;
    long double M;

    cin >> A >> B >> H >> M;

    long double rad;

    rad = pi * 2 * ( (H* 60.0 + M) / (12.0 * 60.0) - M /60.0 ) ;
    long double XX = A*A + B*B - (long double)(2.0 * A*B * cos(rad));
    long double X = sqrt(XX);

    cout << fixed << setprecision(15) << X << endl;
}

Measured memory_bytes: 4128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
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; }


const ll INF = 1e16;

int main(){
    ll n,a,b,c,d,e;
    cin >> n >>a >> b>>c>>d>>e;
    ll M;
    M=min(a,b);
    M=min(c,M);
    M=min(d,M);
    M=min(e,M);
    cout << 5+(n-1)/M << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int a, b, c;
		scanf("%d", &a);
		getchar();
		scanf("%d", &b);
		
		if(a==1 && b==2){
			printf("3\n");
		}
		else if(a==2 && b==1){
			printf("3\n");
		}
		else if(a==3 && b==1){
			printf("2\n");
		}
		else if(a==1 && b==3){
			printf("2\n");
		}
		else if(a==3 && b==2){
			printf("1\n");
		}
		else if(a==2 && b==3){
			printf("1\n");
		}

	return 0;	
} 

Measured memory_bytes: 3148
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
using namespace std;
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int res = 0;
    if(n >= 2)
        res += ((n-1)*n)/2;
    if(m >= 2)
        res += ((m-1)*m)/2;
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
target=int(input())
nums=[]
for i in range(3,target+1):
    nums.append(i)

dp = [0] * (1+target)
for num in nums:
    if num <= target:
        dp[num] = 1
for i in range(target+1):
    for num in nums:
        if i - num > 0:
            dp[i] += dp[i-num]
print(dp[-1]%1000000007)

Measured memory_bytes: 9296
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)



int main(){

    string s;
    cin >> s;
    if(s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
        cout << "Bad" << "\n";
    } else{
        cout <<"Good" << "\n";
    }
}



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

typedef long long ll;

#define REP(i, n) for(int i=0; i<(n); i++)
#define REPS(i, n) for(int i=0; i<=(n); i++)
#define FOR(i, a, b) for(int i=a; i<(b); i++)
#define FORS(i, a, b) for(int i=a; i<=(b); i++)
// for container x
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main(){
    string S;
    cin >> S;
    int ans = 0;
    int cnt = 0;
    for(auto s:S){
        if (s=='A' || s=='C' || s=='G' || s=='T') {
            cnt++;
            ans = max(ans, cnt);
        }
        else {
            cnt =0;
        }
    }

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

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  # dp0[c][j]:c列目の時点で残りちょうどj個取れる時の最大値
  for i in range(R):
    # i+1行目に対する操作
    # 初期化
    for j in range(C):
      dp0[j][3]=max(dp0[j])
      dp0[j][2]=-inf
      dp0[j][1]=-inf
      dp0[j][0]=-inf
    for j in range(C):
      if j>0:
        dp0[j][0]=max(dp0[j][0],dp0[j-1][0])
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print(max(dp0[-1]))
if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)


Measured memory_bytes: 195148
n = int(input())
a = [int(input()) for _ in range(n)]

pushed = set()
cnt = 0
push= 1
while True:
    if push in pushed:
        cnt = -1
        break
    pushed.add(push)
    push = a[push-1]
    cnt += 1
    if push == 2:
        break

print(cnt)
    


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

typedef long long ll;
ll n,k;
pair<ll,ll> p[1010];
ll dp[1010][10010];
ll inf = 1e18;
int main() {
    cin >> k >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p,p+n);
    reverse(p,p+n);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i+1][j] = min(dp[i][j], dp[i+1][j]);
            dp[i+1][min(k,j+p[i].first)] = min(dp[i+1][min(k,j+p[i].first)], dp[i][j] + p[i].second);
            dp[i+1][min(k,j+p[i].first)] = min(dp[i+1][min(k,j+p[i].first)], dp[i+1][j] + p[i].second);
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

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

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

  string a[N];
  string b[M];

  for (int i = 0; i < N; i++) cin >> a[i];
  for (int i = 0; i < M; i++) cin >> b[i];

  for (int i = 0; i <= N - M; i++) {
    for (int j = 0; j <= N - M; j++) {
      // 判定
      bool isMatch = true;
      for (int x = 0; x < M; x++) {
        for (int y = 0; y < M; y++) {
          if (a[x + i][y + j] != b[x][y]) {
            isMatch = false;
            break;
          }
        }
        if (!isMatch) break;
      }

      if (isMatch) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 256
#<D>
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
def main():
    N, Q = map(int ,input().split())
    link = [[] for n in range(N + 1)]
    for n in range(N - 1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    V = [0] * (N + 1)
    for q in range(Q):
        p, x = map(int, input().split())
        V[p] += x
    def dfs(i, parent, acc):
        V[i] += acc
        for j in link[i]:
            if j != parent:
                dfs(j, i, V[i])

    cur = 1
    parent = 0
    acc = 0
    dfs(cur, parent, acc)
    V = [str(i) for i in V]
    print(" ".join(V[1:]))

if __name__ == "__main__":
    main()



Measured memory_bytes: 283124
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp(a,b) make_pair(a,b)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
int main(){
    string s;
    cin>>s;
    string t;
    cin>>t;
    int n = s.length();
    int tn = t.length();
    int mined = 100000;
    rep(i,n){
        int ed=0;
        string subs =s.substr(i,tn);
        if(subs.length()<tn)break;
        rep(j,tn){
            if(subs[j]!=t[j]){
                ed++;
            }
        }
        mined = min(mined,ed);
    }
    cout<<mined<<endl;
}

Measured memory_bytes: 3624
n = int(input())
v = list(map(int, input().split()))
v1 = {}
for i in range(0, n, 2):
    v1.setdefault(v[i], 0)
    v1[v[i]] += 1
v2 = {}
for i in range(1, n, 2):
    v2.setdefault(v[i], 0)
    v2[v[i]] += 1
v1 = [(i, j) for i, j in v1.items()]
v2 = [(i, j) for i, j in v2.items()]
v1.sort(key = lambda x: x[1])
v2.sort(key = lambda x: x[1])
if v1[-1][0] != v2[-1][0]:
    print(n - v1[-1][1] - v2[-1][1])
else:
    if len(v1) == 1:
        if len(v2) == 1:
            print(n // 2)
        else:
            print(n - v1[-1][1] - v2[-2][1])
    elif len(v2) == 1:
        print(n - v1[-2][1] - v2[-1][1])
    else:
        print(min(n - v1[-1][1] - v2[-2][1], (n - v1[-2][1] - v2[-1][1])))

Measured memory_bytes: 19676
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n, a, b;
int main(int argc, char const *argv[])
{
	scanf("%d%d%d", &n, &a, &b);
	printf("%d\n", min(n*a, b));
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int		main()
{
	int		X;
	int		ans;

	ans = 0;
	scanf("%d\n", &X);
	if (X >= 500)
	{
		ans = (X / 500) * 1000;
		X %= 500;
	}
	if (X >= 5)
		ans += (X / 5) * 5;
	printf("%d\n", ans);
	return (0);
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N = int(input())
    #h = list(map(int, input().split()))
    h = [int(x) for x in input().split()]
    inf = float("inf")
    dp = [inf]*(N)

    #2:初期値
    dp[0] = 0

    #3:dp実行部(貰うDP)
    for i in range(1,N):
        dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
        if(i>1): #2つ目の足場には二個前の足場がないので．
            dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

    # #3:dp実行部(配るDP)
    # for i in range(N):
    #     if(i+1<N):
    #         dp[i+1] = min(dp[i+1], dp[i] + abs(h[i] - h[i+1]))
    #     if(i+2<N):
    #         dp[i+2] = min(dp[i+2], dp[i] + abs(h[i] - h[i+2]))

    #4:出力
    print(dp[N-1])

if __name__ == '__main__':
    main()

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


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

    unordered_map<i64, i64> r2a;
    REPS(i, 1000) {
        r2a[i * i] = i;
    }

    auto f = [&](i64 x, i64 y, i64 z) {
        return x * x + y * y + z * z + x * y + y * z + z * x;
    };

    const i64 lim = 100;
    REPS(n, N) {
        i64 cnt = 0;
        REPS(x, lim) {
            REPS(y, lim) {
                i64 B = x + y;
                i64 C = x * x + y * y + x * y - n;
                i64 det = B * B - 4 * C;
                if (det < 0) continue;
                i64 a = -1;
                if (det == 0) a = 0;
                else if (r2a[det] > 0) a = r2a[det];
                if (a == -1) continue;

                i64 denom = a - B;
                if (denom % 2 != 0) continue;
                i64 z = denom / 2;
                if (z <= 0) continue;

                assert(f(x, y, z) == n);
                cnt++;
            }
        }
        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 4156
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mx 100005
vector<ll>prime;
bool vis[mx];
void seive()
{
    ll x=sqrt(mx);
    for(int i=3;i<=x;i+=2)
    {
        if(vis[i]==false)
        {
            for(int j=i*i;j<mx;j+=2*i)
            {
                vis[j]=true;
            }
        }
    }
    prime.pb(2);
    for(int i=3;i<mx;i+=2)
    {
        if(vis[i]==false)
        {
             prime.pb(i);
        }

    }


}
int main()
{

    seive();
    ll n;
    cin>>n;
    ll x=lower_bound(prime.begin(),prime.end(),n)-prime.begin();
    cout<<prime[x]<<endl;



}



Measured memory_bytes: 3844
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
int main(){
int A, B, C, K; cin >> A >> B >> C >> K;
REP(i, K){ if(A>=B){ B=2*B; }else if(B>=C){ C=2*C; } }
if(A<B&&B<C){ cout << "Yes\n"; }else{ cout << "No\n"; }
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
static const int INF=(1<<21);
int n,m[101][101];
int d[101];
void bfs(int s){
  queue<int>q;
  q.push(s);
  for(int i=0;i<n;i++){
    d[i]=INF;
  }
  d[s]=0;
  while(!q.empty()){
    int u=q.front();
    q.pop();
    for(int v=0;v<n; v++){
      if(m[u][v]==0){
	continue;
      }
      if(d[v]!=INF){
	continue;
      }
      d[v]=d[u]+1;
      q.push(v);
    }
  }
  for(int i=0;i<n;i++){
    cout<<i+1<<" "<<( (d[i]==INF)?(-1):d[i] )<<endl;
  }
}
int main(){
  int u,k,v;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v;
      m[u-1][v-1]=1;
    }
  }
  bfs(0);
  return(0);
}



Measured memory_bytes: 3144
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    # path search init
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex] + current_adj_weight
                if alt_path < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex))
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Measured memory_bytes: 8900