akhauriyash/Code-Regression huggingface dataset:
A, B, C, D = gets.split.map &:to_i
ret = 0
if B < C || D < A
    ret = 0
elsif C <= A && B <= D
    ret = B - A
elsif C <= A && D <= B
    ret = D - A
elsif A <= C && D <= B
    ret = D - C
elsif A <= C && B <= D
    ret = B - C
end
puts ret

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
typedef long long ll;
int n;
ll s1[maxn],s2[maxn],x[maxn],v[maxn],c,ans;
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%d %lld",&n,&c);
	for (int i=1;i<=n;i++)
		scanf("%lld %lld",&x[i],&v[i]);
	ll tmp=0,lst=0;
	for (int i=1;i<=n;i++) {
		tmp+=v[i]; tmp-=x[i]-lst;
		lst=x[i];
		s1[i]=max(s1[i-1],tmp);
	}
	tmp=0; lst=c;
	for (int i=n;i>=1;i--) {
		tmp+=v[i]; tmp-=lst-x[i];
		lst=x[i];
		s2[i]=max(s2[i+1],tmp);
	}
	for (int i=0;i<=n;i++) {
		//printf("%lld %lld\n",s1[i],s2[i]);
		ans=max(ans,s1[i]);
		ans=max(ans,s2[i]);
		tmp=s1[i]+s2[i+1]-x[i];
		ans=max(ans,tmp);
		tmp=s2[i]+s1[i-1]-(c-x[i]);
		ans=max(ans,tmp);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3328
/* ITP1_1_D */

import java.io.*;
import java.util.*;

public class Main {
    public static void main (String[] args) throws java.lang.Exception {
    
    BufferedReader input = new BufferedReader (new InputStreamReader(System.in));
    String txt = input.readLine();
    int text = Integer.parseInt(txt);
    int h = (text / 3600);
    int m = ((text % 3600) / 60);
    int s = (text % 60);
    System.out.println(h + ":" + m + ":" + s);
    
    }
}


Measured memory_bytes: 24376
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 10**12

for i in range(2**N):
  #print(i,bin(i).count('1'))
  # 左から見える数がK未満ならスキップ
  if bin(i).count('1') < K:
    pass
  # 1番左が見えない(0)は無理なのでpass
  elif (i >> 0) & 0:
    pass
  else:
    tmp = [None]*N
    tmp[0] = A[0]
    tmpAns = 0
    for j in range(1,N):
      maxLeft = max(tmp[:j],default=0)
      if (i >> j) & 1:#左から見える
        if maxLeft < A[j]:# 左側のどれよりも高い
          tmp[j] = A[j]
        else:
          tmp[j] = maxLeft+1
          tmpAns += maxLeft+1-A[j]            
      else:#左から見えない
        if maxLeft >= A[j]:# 元から見えてない
          tmp[j] = A[j]
        else:# 左から見えているので一番高いところをもっと高くして隠す
          tmp[j] = A[j]
          tmpIndex = tmp[:j].index(maxLeft)
          tmp[tmpIndex] = tmp[j]
          tmpAns += tmp[j] - maxLeft
    if tmpAns < ans:
      ans = tmpAns
print(ans)

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); 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)

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 (a>b) { a=b; return 1; } return 0; }

#define ld long 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;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x; cin>>x;
    if (x<1200){
        cout<<"ABC\n";
    }else{
        cout<<"ARC\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdlib.h>
#include<map>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
#include<cstdlib>
const int MAX=1e5+10;
int n,m;
struct lll
{
    int x,y;
}a[MAX],b[MAX];
int mp[MAX];
int dp[110][110];
int lianjie[110];
int c[110][110];
int balalanengliang(int t)
{
    for(int i=1;i<=n;i++)
    {
        //cout<<t<<"_"<<i<<"_"<<mp[i]<<"_"<<c[t][i]<<endl;
        if(!mp[i]&&c[t][i])
        {
            //cout<<t<<"_"<<i<<endl;
            mp[i]=1;
            if(!lianjie[i]||balalanengliang(lianjie[i]))
            {
                lianjie[i]=t;
                //cout<<t<<"_"<<i<<endl;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(lianjie,0,sizeof(lianjie));
    memset(mp,0,sizeof(mp));
    cin>>n;
    int sum=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
        cin>>b[i].x>>b[i].y;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i].x<b[j].x&&a[i].y<b[j].y)
            {
                c[i][j]=1;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        memset(mp,0,sizeof(mp));
        if(balalanengliang(i))
            sum++;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>

#define int long long

signed main(){
	int N, P, i;
	scanf("%lld%lld", &N, &P);
	int *A = (int *)malloc(sizeof(int) * (N + 1));
	int *odd = (int *)malloc(sizeof(int) * (N + 1));
	int *even = (int *)malloc(sizeof(int) * (N + 1));
	for(i = 1; i <= N; i++){
		scanf("%lld", &A[i]);
	}
	odd[0] = 0;
	even[0] = 1;
	for(i = 1; i <= N; i++){
		if(A[i] % 2 == 0){
			odd[i] = 2 * odd[i - 1];
			even[i] = 2 * even[i - 1];
		}
		else{
			odd[i] = odd[i - 1] + even[i - 1];
			even[i] = odd[i - 1] + even[i - 1];
		}
	}
	if(P == 0){
		printf("%lld\n", even[N]);
	}
	else{
		printf("%lld\n", odd[N]);
	}
	return 0;
}

Measured memory_bytes: 128
#%%

num2alpha = lambda c: chr(c+64)

h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
     s[i] = list(input().split())
     for j in range(w):
        if s[i][j] == 'snuke':
            a = i + 1
            b = num2alpha(j + 1)

print(str(b)+str(a))








#%%


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n, k;
  while (cin >> n >> k) {
    if (n == 0 && k == 0) break;
    vector<int> card;
    REP(i, n) {
      int c;
      cin >> c;
      card.push_back(c);
    }
    sort(ALL(card));
    map<int, int> mp;
    do {
      int num = 0;
      REP(i, k) {
        if (i == 0) {
          num += card[i];
        } else {
          int d = 0;
          int tmp = card[i];
          while (0 < tmp) {
            tmp /= 10;
            d++;
          }
          REP(j, d) num *= 10;
          num += card[i];
        }
      }
      mp[num]++;
    } while (next_permutation(ALL(card)));
    cout << mp.size() << endl;
  }
  return 0;
}


Measured memory_bytes: 3168
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int main() {
    ll L, R;
    cin >> L >> R;

    if ((R - L + 1) >= 2019)
        cout << 0 << endl;
    else {
        ll ans = infl;
        for (ll i = L; i <= R; ++i) {
            for (ll j = i + 1LL; j <= R; ++j) {
                ans = min(ans, (i % 2019) * (j % 2019) % 2019);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(M)]

island = list(range(N))
counts = [1] * N
total = int((N * (N - 1)) / 2)
result = []

for c in reversed(data):
    ref0 = int(c[0]) - 1
    while island[ref0] != ref0:
        ref0 = island[ref0]
    ref1 = int(c[1]) - 1
    while island[ref1] != ref1:
        ref1 = island[ref1]

    if ref0 == ref1:
        result.append(0);
    else:
        island[max(ref0,ref1)] = min(ref0, ref1)
        result.append(counts[ref0] * counts[ref1]);
        counts[min(ref0,ref1)] = counts[ref0] + counts[ref1]

res = [total]
for r in result:
    res.append((res[-1] - r))

print('\n'.join(reversed([str(x) for x in res][:-1])))


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

int main() {
	int sx, sy, tx, ty;
	std::cin >> sx >> sy >> tx >> ty;
	int dx = tx - sx;
	int dy = ty - sy;
	std::cout << std::string(dy, 'U') << std::string(dx, 'R');
	std::cout << std::string(dy, 'D') << std::string(dx + 1, 'L');
	std::cout << std::string(dy + 1, 'U') << std::string(dx + 1, 'R');
	std::cout << "DR" << std::string(dy + 1, 'D') << std::string(dx + 1, 'L') << 'U' << '\n';

	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MOD = 1e9+7;

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

    int k,a,b;
    cin >> k >> a >> b;

    bool ok = false;
    rep(i,1001){
        if(i%k != 0) continue;
        if(i>=a && i<=b) ok = true;
    }

    cout << ( ok ? "OK" : "NG" ) << endl;

    return 0;
}


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

int main(){
   int h, w;
   while(1){
   cin >> h >> w;
   if( h == 0 && w == 0) break;
   for(int a = 0;a < h; a++){
    for(int b = 0; b < w; b++){
     if(a % 2 == 0){
      if( b % 2 == 0) cout << "#";
      else cout << ".";
     } else{
        if(b % 2  == 0) cout << ".";
        else cout << "#";
     }
    }
   cout << endl;
   }
  cout << endl;
 }
return 0;
}

Measured memory_bytes: 1152
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		if ( A >= B ){
			System.out.println("delicious");
		}else if ( A+X >= B ){
			System.out.println("safe");
		}else{
			System.out.println("dangerous");
		}
	}
}


Measured memory_bytes: 25040
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
import Data.Array.IArray
--import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
dictCompare :: [a -> a -> Ordering] -> a -> a -> Ordering
dictCompare [] _ _ = EQ
dictCompare (f:fs) x y = let c = f x y in if c==EQ then dictCompare fs x y else c
-- end of templete



main = do
    [n, m] <- getInts
    list <- zip [1..] <$> replicateM n getInt
    bs <- replicateM m getInt
    print . head . maximumBy (comparing length) . group . sort $ [fst $ head $ filter ((<=b) . snd) list | b <- bs]


Measured memory_bytes: 4844
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    const long double EPS = 1e-14;
    ll A, B, C; cin >> A >> B >> C;
    if(sqrtl(A) + sqrtl(B) + EPS < sqrtl(C)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main()
{
	ll n;
	cin>>n;
	
	map<ll,ll>mapper;
	ll sum=0;
	for(int i=0;i<n;i++)
	{
		int temp;
		cin>>temp;
		
		sum+=temp;
		mapper[temp]++;
	}
	
	int test;
	cin>>test;
	while(test--)
	{
		ll x,y;
		cin>>x>>y;
		
		ll xCount=mapper[x];
		
		mapper[x]=0;
		mapper[y]+=xCount;
		
		sum-=xCount*x;
		sum+=xCount*y;
		
		cout<<sum<<endl;
	}
	return 0;
}

Measured memory_bytes: 9416
#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
typedef long long ll;
using namespace std;
class activity{
public:
	int swim, bugs, hw;
};
int  max(int a, int b){
	return a > b ? a : b;
}
int main(){
	int n;
	//freopen("input.txt", "r", stdin);
	cin >> n;
	assert(n>=0);
	vector<activity>v(n);
	for (int i = 0; i < n; i++){
		cin >> v[i].swim >> v[i].bugs >> v[i].hw;
	}
	vector<vector<int>>dp(n, vector<int>(3,0));
	dp[0][0] = v[0].swim;
	dp[0][1] = v[0].bugs;
	dp[0][2] = v[0].hw;
	for (int i = 1; i < n; i++){
		dp[i][0] = v[i].swim + max(dp[i-1][1],dp[i-1][2]);
		dp[i][1] = v[i].bugs + max(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = v[i].hw + max(dp[i - 1][1], dp[i - 1][0]);
	}
	cout << max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2])<<endl;
	return 0;
}

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> p(N);

    for(int i = 0; i < N; i++){
        cin >> p[i];
    }

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

    int ans = 0;
    for(int i = 0; i < K; i++){
        ans += p[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    size_t n;
    scanf("%zu", &n);

    std::vector<std::string> S(n);
    for (size_t i=0; i<n; ++i) {
        char buf[64];
        scanf("%s", buf);
        S[i] = buf;
    }

    for (char c='a'; c<='z'; ++c) {
        int min=64;
        for (std::string &s: S)
            min = std::min<int>(min, std::count(s.begin(), s.end(), c));

        for (int i=0; i<min; ++i)
            putchar(c);
    }

    printf("\n");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ft first
#define sd second
#define pb push_back
using namespace std;
const int mod = 1e9+7;
const int N = 1e5+9;

int a[N];

signed main() {  

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
 	int n; cin >> n;
 	vector<int> ans;
 	for(int i = 1; i <= n; i++) {
 		cin >> a[i];
 	}
 	vector<bool> done(n+1);
 	for(int i = 1; i <= n; i++) {
 		int cnt = 0, ind = 0;
 		for(int j = 1; j <= n; j++) {
 			if(done[j] == 0) {
 				cnt++;
 				if(cnt == a[j]) ind = j;
 			}
 		}
 		if(ind == 0) return cout << -1, 0;
 		ans.pb(ind);
 		done[ind] = 1;
 	}
 	reverse(ans.begin(), ans.end());
 	for(int i: ans) cout << a[i] << "\n";

    return 0;
    
}

Measured memory_bytes: 256
<?php
 
fscanf(STDIN, '%d', $n);
for ($count = 0; $count < $n; $count++) {
    $a = explode(' ', trim(fgets(STDIN)));
    $b = 0;
    $c = 0;
    for ($i = 0; $i < 10; $i++) {
    	$diff_ab = $a[$i] - $b;
    	$diff_ac = $a[$i] - $c;
        if ($diff_ab > 0 && $diff_ac > 0) {	//どちらの筒にも入れられる場合
        	if ($diff_ab <= $diff_ac){	//左の筒に入れた方が既存の玉との差が小さくなる場合
            	$b = $a[$i];
        	} else {
        		$c = $a[$i];
        	}
        } else if ($diff_ab > 0) {	//左の筒にしか入れられない場合
            $b = $a[$i];
        } else if ($diff_ac > 0) {	//右の筒にしか入れられない場合
        	$c = $a[$i];
        } else {
            break;
        }
    }
 
    echo $i === 10 ? 'YES' : 'NO';
    echo PHP_EOL;
}

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

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

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

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

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

int main() {
    int N;
    ll D;
    cin>>N>>D;
    int ans = 0;
    rep(i,N){
        ll X,Y;
        cin>>X>>Y;
        if(X*X+Y*Y<=D*D) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3640
#include <stdio.h>
#define MAX 3000

int main(void)
{
  int i, j,n,count = 0;
  int p[1000000];

  //---初期化---
  while(scanf("%d",&n) != EOF){
  	count = 0;
  for(i=0 ; i<n ; i++) p[i] = 0;
  p[0] = 1;
  //---倍数を除外---
  for(i=2 ; i<=n/2 ; i++){
    for(j=2 ; i*j<=n ; j++){
      if(p[i*j-1] == 0)
        p[i*j-1] = 1;
    }
  }
  for(i=0 ; i<n ; i++){
    if(p[i] == 0)
      count = count + 1;
  }
  printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 4504
/*  
	Jatin Tayal
	MNNIT, CSE
	Live Everyday Like It's Your Last !
*/

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define boost ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n"; 
#define tr(container, it)  for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define all(c) (c).begin(),(c).end() 

typedef long long int ll;
typedef pair<ll,ll> pii;
typedef priority_queue< pii , vector< pii > , greater< pii > > pq;

const ll N = 2e5+10;
const ll MOD = 1000000007;

ll n, m, vis[N], pos[N], pnt[N];
vector<ll> v[N],par[N], tmp;
stack<ll> st;

void dfs(ll node){
	vis[node] = 1;
	ll i;
	for(i=0;i<v[node].size();i++){
		ll child = v[node][i];
		if(!vis[child])
			dfs(child);
	}
	st.push(node);
}


int main(){
	boost;
	cin>>n>>m;
	ll i,j;
	for(i=0;i<n-1+m;i++){
		ll x,y;
		cin>>x>>y;
		v[x].pb(y);
		par[y].pb(x);
	}

	for(i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);

	ll cnt=0;
	while(!st.empty()){
		pos[st.top()] = cnt;
		cnt++;
		tmp.pb(st.top());
		st.pop();
	}

	// pnt[tmp[0]] = 0;
	for(i=0;i<n;i++){
		ll node = tmp[i],maxi=-1,res=0;
		for(j=0;j<par[node].size();j++){
			ll avl = par[node][j];

			if(pos[avl]>maxi){
				maxi = pos[avl];
				res = avl;
			}
		}
		pnt[node] = res;
		// debug2(node,res);
	}
	for(i=1;i<=n;i++)
		cout<<pnt[i]<<endl;	

	return 0;
}

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

#include <unistd.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
 
 
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx_ori[4] = { -1,0, 1,0 }, dy_ori[4] = { 0,1,0,-1 };
int dx[4] = {0, 0, 0, 0}, dy[4] = {0, 0, 0, 0};
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
// #define mp make_pair
//#define endl '\n'

signed main() {
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  if (n <= k) {
    cout << x * n << endl;
  }
  else {
    cout << x * k + y * (n - k) << endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;

class Test
{

    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var arr = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        Array.Sort(arr, (x, y) => { return y.CompareTo(x); });
        long h = 0;
        long w = 0;
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] == arr[i - 1])
            {
                if (h == 0)
                    h = arr[i];
                else if (w == 0)
                    w = arr[i];
                i++;
            }

            if (h != 0 && w != 0)
                break;


        }
        Console.Write(h * w);

    }

}

















Measured memory_bytes: 28880
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int gcd(int a,int b)
{
	if(b==0)
	return a;
	
	return gcd(b,a%b);
}
int power(int x,int y,int p)
{
	int res=1;
	x=x%p;
	while(y>0)
	{
		if(y&1)
		res=(res*x)%p;
		
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
int modInverse(int n,int p)
{
	return power(n,p-2,p);
}
int main() {
	// your code goes here
	 ios_base::sync_with_stdio(0);
	 cin.tie(0);
	 int n;
	 cin>>n;
	 map<int,int> mp;
	 for(int x=1;x<sqrt(n);x++)
	 {
		 for(int y=1;y<sqrt(n);y++)
		 {
			 for(int z=1;z<sqrt(n);z++)
			 {
				 int val = x*x+y*y+z*z+x*y+y*z+z*x;
				 if(val<=n)
				 mp[val]++;
				 else
				 break;
			 }
		 }
	 }
	 for(int i=1;i<=n;i++)
	 {
		 cout<<mp[i]<<'\n';
	 }
	 return 0;
}


Measured memory_bytes: 4016
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node{
	unsigned int key;
	struct Node *next;
	struct Node *prev;
};

typedef struct Node  *NodePointer;

NodePointer nil;

NodePointer listSearch(int key)
{
	NodePointer cur = nil->next;
	while(cur!=nil && (cur->key != key)){
		cur = cur->next;
	}
	return cur;
}
	

void init()
{
	nil=malloc(sizeof(struct Node));
	nil->next=nil;
	nil->prev=nil;
}

void printList()
{
	NodePointer cur = nil->next;
	int isf=1;
	while(1){
		if(cur==nil){break;}
		if(isf==0){printf(" ");}
		printf("%d", cur->key);
		cur=cur->next;
		isf=0;
	}
	printf("\n");
}

void deleteNode(NodePointer t)
{
	t->next->prev=t->prev;
	t->prev->next=t->next;
	free(t);
}
 
void deleteFirst()
{
	NodePointer t= nil->next;
	if(t==nil) return;
	deleteNode(t);
}

void deleteLast()
{
	NodePointer t= nil->prev;
	if(t==nil) return;
	deleteNode(t);
}

void deleteKey(int key)
{
	NodePointer x = nil->next;
	
	for(x=nil->next; x!=nil; x=x->next){
		if(x->key==key){
			if(x->next==nil){
				deleteLast();
			}
			else if(x->prev==nil){
				deleteFirst();
			}
			else{
				deleteNode(x);
			}
			break;
		}
	}
}

void insertKey(int key)
{
	NodePointer x;
	x = malloc(sizeof(struct Node));
	x->key=key;
	x->next=nil->next;
	x->prev=nil;
	nil->next->prev=x;
	nil->next=x;
}
int main(void)
{
	int i,n,key,size=0, np=0, nd=0;
	char com[20];
	
	
	scanf("%d", &n);
	init();
	for(i=0;i<n;i++){
		scanf("%s%d", com, &key);
		if(com[0]=='i'){
			insertKey(key);
			np++;
			size++;
		}
		else if(com[0]=='d'){
			if(strlen(com)>6){
				if(com[6]=='F') deleteFirst();
				else if(com[6]=='L') deleteLast();
			}
			else{
				deleteKey(key);
				nd++;
			}
			size--;
		}
	}
	printList();
	return 0;
}
	
	


Measured memory_bytes: 32996
<?php
fscanf(STDIN, "%d", $n);
if ($n % 2 === 0) {
    $oddNum = $n / 2;
    echo $oddNum / $n;
} else if($n % 2 === 1) {
    $oddNum = intdiv($n, 2) + 1;
    echo $oddNum / $n;
}


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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

int main() {
    string s, t;
    cin >> s >> t;
    int cnt = 0;
    REP(i, s.length()) {
        if(s[i] == t[i]) cnt++;
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#region using directives
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Convert;
#endregion

namespace for_contests
{
    class Program
    {
        static int Compare1(KeyValuePair<long, long> a, KeyValuePair<long, long> b)
        {
            return a.Key.CompareTo(b.Key);
        }
        static void Main(string[] args)
        {
            int N = ToInt32(ReadLine());
            long f = 0;
            long answ = 0;
            for (int i = 0; i < N; i++)
            {
                string[] s = (ReadLine()).Split();
                int x = ToInt32(s[0]);
                int y = ToInt32(s[1]);
                if (x > f)
                {
                    f = x;
                    answ = x + y;
                }
            }
            WriteLine(answ);
            ReadKey();
        }
    }
}


Measured memory_bytes: 17336
class UnionFind:
    """1-index"""

    def __init__(self, n):
        self.parent = [-1] * (n + 1)  # parentは親の番号を格納。親だった時は-サイズを格納。

    # 親の番号を返す
    def root(self, A):
        if self.parent[A] < 0:
            return A
        else:
            return self.root(self.parent[A])

    # サイズを返す
    def size(self, A):
        return - self.parent[self.root(A)]

    # AとBをくっつける(直接ではなくroot(A)とroot(B)を繋げる)
    def unite(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if A == B:  # 既に同じ塊内にいる
            return False

        if self.size(A) < self.size(B):
            A, B = B, A

        self.parent[A] += self.parent[B]  # サイズを更新
        self.parent[B] = A

        return True

    # AとBが同じグループに属しているかを調べる.
    def same_check(self, A, B):
        return self.root(A) == self.root(B)


N, M = map(int, input().split())

ans = N * (N - 1) // 2
result = [ans]
uf = UnionFind(N)
A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

for i in reversed(range(1, M)):
    if not uf.same_check(A[i], B[i]):
        ans -= uf.size(A[i]) * uf.size(B[i])
        uf.unite(A[i], B[i])
    result.append(ans)


for i in reversed(result):
    print(i)


Measured memory_bytes: 16952
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	ll x;
	cin >> x;
	ll res = 1;
	FOR(i, 2, x) FOR(j, 2, 11) {
		ll v = 1;
		REP(k, j) v *= i;
		if (v <= x) res = max(res, v);
	}
	cout << res << endl;
	return 0;
}
 

Measured memory_bytes: 256
N = int(input())
L = list(map(int,input().split()))
ijk = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] != L[j] and L[j] != L[k] and L[i] != L[k]:
                if L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
                    ijk+=1
print(ijk)

Measured memory_bytes: 9204
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
int main(void)
{
	int n,h,m,a;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d:%d",&h,&m);
		h=h*60+m;
		m*=12;
		a=std::min(abs(h-m),std::min(abs(h+720-m),abs(h-720-m)));
		if(a<60)
			puts("alert");
		else if(a>=180)
			puts("safe");
		else puts("warning");
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
para = [i for i in map(int,input().split())]
"""
(a_1-1)+a_1*x_1 = (a_2-1)+a_2*x_2 = .... = (a_i-1)+a_i*x_i  = .... = (a_n-1)+a_n*x_nの解は存在する
"""
ans = 0 
for i in para :
    ans += i - 1
print(ans)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005

void solve()
{
    ll n,k=2,l;
    cin>>n;
    ll dp[n+1];
    ll h[n+1];
    rep(i,1,n+1)cin>>h[i];
    dp[n]=0;
    for(int i=n-1;i>0;i--)
    {
        dp[i]=hell;
        rep(j,1,k+1)
        {
            l=min(n,i+j);
            dp[i]=min(dp[i],dp[l]+abs(h[i]-h[l]));
        }
    }
    // rep(i,1,n+1)
    // {
    //     cout<<dp[i]<<" ";
    // }
    cout<<dp[1]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 5160
/*
如果H是h的倍数且W是w的倍数，那么整个矩阵可以看成是被(H / h) * (W / w)个h * w的子矩形覆盖。若每个子矩形和为负数，整个矩形和也一定为负数，故无解
下面给出这么一种构造方法：考虑H是h的倍数和W是w的倍数两个条件最多一个成立时，取一维上不是倍数的。以H不是h的倍数为例
将行从0开始编号。若第p mod h = 0，那么第p行全填V * (h - 1) - 1，否则第p行全填-V。那么有： 
(1)对于每个h * w的子矩阵，恰好跨越1个编号mod h = 0的行和h - 1个编号mod h > 0的行，元素和 = ((V * (h - 1) - 1) * 1 - V * (h - 1)) * w = -w
(2)对于整个矩阵，考虑把所有行按照ceil(p / H)分段，每一个完整的段和都是-W。对于不完整的段，贡献显然是个关于V的一次函数kV + b，其中k > 0
那么取一个很大的V（满足填的数不超过上限）即可，手算一下发现满足条件 
*/

#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_HW(505);

int H, W, h, w, Ans[Max_HW][Max_HW], V;
bool Rev;

int main()
{
	scanf("%d%d%d%d", &H, &W, &h, &w);
	if (H % h == 0 && W % w == 0)
	{
		puts("No");
		return 0;
	}
	if (H % h == 0)
		swap(H, W), swap(h, w), Rev = true;
	V = 1000000;
	for (int i = 0;i <= H - 1;++i)
		if (i % h == 0)
			for (int j = 0;j <= W - 1;++j)
				Ans[i][j] = V * (h - 1) - 1;
		else
			for (int j = 0;j <= W - 1;++j)
				Ans[i][j] = -V;
	puts("Yes");
	if (Rev)
	{
		swap(H, W);
		for (int i = 0;i <= H - 1;++i)
		{
			for (int j = 0;j <= W - 1;++j)
				printf("%d ", Ans[j][i]);
			printf("\n");
		}
	}
	else
		for (int i = 0;i <= H - 1;++i)
		{
			for (int j = 0;j <= W - 1;++j)
				printf("%d ", Ans[i][j]);
			printf("\n");
		}
	return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, m, q;
  cin >> n >> m >> q;

  vector<vector<int>> cnt(n, vector<int>(n, 0));
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cnt[l][r]++;
  }

  vector<vector<int>> psum(n);
  for (int i = 0; i < n; ++i) {
    psum[i].push_back(0);
    partial_sum(cnt[i].begin(), cnt[i].end(), back_inserter(psum[i]));
  }

  vector<int> ans;
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;

    int a = 0;
    for (int j = l; j <= r; ++j) {
      a += psum[j][r + 1] - psum[j][l];
    }

    ans.push_back(a);
  }

  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << '\n';
  }

  return 0;
}


Measured memory_bytes: 3456
//----->|try=0; while(!success) try++;|<------
//----->|Belief Yourself,Respect Yourself|<----
//----->|Be Proud Of Yourself,You're Doing Your best|<-----
#include<bits/stdc++.h>
using namespace std;
#define uniq(x)  x.erase(unique(x.begin(),x.end()), x.end()) //Unique value find from vector
#define upper(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Upper value search;
#define lower(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Lower value search;
#define max3(a,b,c) max(max(a,b),c)//maximum value find three value;
#define min3(a,b,c) min(min(a,b),c)//minimum value find three value;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, n) for(int i = 1; i <= n; ++i)
#define rep1(i,start,n) for(int i=start;i<n;++i)
#define PI acos(-1.0)//PI Calculation
#define LL long long
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a)|(b))
#define XOR(a,b) ((a) ^ (b))
#define MP make_pair
#define sqr(x) ((x)*(x))
#define sqrt(x) sqrt(1.0*(x))
#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define MX 1000005
#define MOD 1000000007
template<typename T> T POW(T b,T p)          //Pow calculation
{
    T r=1;
    while(p)
    {
        if(p&1)r=(r*b);
        b=(b*b);
        p>>=1;
    }
    return r;
}

template<typename T> T BigMod(T b,T p,T m) //BigMod Calculation
{
    T r=1;
    while(p)
    {
        if(p&1)r=(r*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return r;
}

//||--------------------------->||Main_Code_Start_From_Here||<---------------------------------||
int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int n,ar[100001];
    while(cin>>n)
    {
        memset(ar,-1,sizeof(ar));
        int k=0;
        int sum=0;
        REP(i,n)
        {
            sum+=i;
            if(sum==n)
            {
                ar[i]=i;
                break;
            }
            ar[i]=i;
            if(sum>n)
            {
               int t=sum-n;
               ar[t]=-1;
               break;
            }
            k++;
        }

        //check
        REP(i,k+1)
        {
            if(ar[i]!=-1) cout<<ar[i]<<endl;
        }

    }

}



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

int main() {
  long double a,b,c;
  cin >> a >> b >> c;
  if(2*sqrtl(a*b)+a+b < c){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
  
      
 
}

// int型の2次元配列(3×4要素の)の宣言
  //vector<vector<int>> data(3, vector<int>(4));
 
  // 入力 (2重ループを用いる)
  //for (int i = 0; i < 3; i++) {
    //for (int j = 0; j < 4; j++) {
      //cin >> data.at(i).at(j);
   // }
  //}


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

int main(){
	int n;
	cin >> n;
	int a[n],front_gcd[n],back_gcd[n],gcd;
	int max = 0;
	for(int i = 0; i < n;i++){
		cin >> a[i];
	}
	for(int i = 0; i < n;i++){
		if(i == 0){
			front_gcd[0] = a[0];
		}else{
			front_gcd[i] = __gcd(front_gcd[i-1],a[i]); 
		}
	}
	for(int i = n-1;i >= 0;i--){
		if(i == n-1){
			back_gcd[n-1] = a[n-1];
		}else{
			back_gcd[i] = __gcd(back_gcd[i+1],a[i]);
		}
	}
	for(int i = 0;i < n; i++){
		if(i == 0){
			max = back_gcd[1];
		}else if(i == n-1 && front_gcd[n-2] > max){
			max = front_gcd[n-2];
		}else{
			gcd = __gcd(front_gcd[i-1],back_gcd[i+1]);
			if(gcd > max){
				max = gcd;
			}
		}
	}
	cout << max << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define Mod 1000000007
#define INF 9999999999
#define INFL 99999999999
#define EPS 1e-9
#define pb push_back
#define mp make_pair
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define N 100005
#define fs first
#define sc second 
using namespace std;
typedef  long long int ll;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;
typedef vector <ll> vi;

int gcd(int a, int b)
{
    // Everything divides 0 
    if (a == 0 || b == 0)
       return 0;
 
    // base case
    if (a == b)
        return a;
 
    // a is greater
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}

int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
ios::sync_with_stdio(false);
 cin.tie(0);
ll arr[N];
ll n,k=0;

cin>>n;
if(n==1)
{

    cout<<0<<endl;
    return 0;
}
for(int i=0;i<n;i++)
    cin>>arr[i];
for(int i=0;i<n;i++)
{
    if(arr[i]==i+1)
    {
        swap(arr[i],arr[i+1]);
        k++;
    }
}

cout<<k<<endl;








return 0;

}


Measured memory_bytes: 1024
from collections import deque

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

Measured memory_bytes: 55260
import numpy as np
import itertools
# coin tanka
tanka = np.array([500, 100, 50])
count = 0
A = int(input())
B = int(input())
C = int(input())
X = int(input())

# each pattern
a = [a for a in range(A+1)]
b = [b for b in range(B+1)]
c = [c for c in range(C+1)]

# all patterns
itr_res = np.array(list(itertools.product(a, b, c)))

# remove 0 0 0  pattern
itr_res = itr_res[1:]

for r in itr_res:
    # seach for X  with total price
    if X == sum(r * tanka):
        count += 1
print(count)

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

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

  int x;
  cin >> x;

  if(x >= 30) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <math.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

int main () {
    int weight[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    int x;
    while(cin>>x){
        for(int i=0; i<=1023; i++){
            int bit =i;
            int sum =0;
            for(int j=0; j<10; j++){
                if(bit%2==1){
                    sum+=weight[j];
                }
                bit=bit/2;
            }
            
            if(sum == x){
                int flag = 0;
                for(int j=0; j<10; j++){
                    if(i%2==1&&flag==0){
                        cout<<weight[j];
                        flag++;
                    }else if(i%2==1){
                        cout<<" "<<weight[j];
                    }
                    i=i/2;
                }
                cout<<endl;
                break;
            }
            
            
            
        }
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

string str;

struct u{
	string bk;
	u(){bk="000000000000000000000000000";}
	void gao(){
		for(int i=0;i<str.length();i++){
			bk[str[i]-'a'+1]++;
		}
	}
	friend bool operator == (u a,u b){
		for(int i=1;i<=26;i++){
			if(a.bk[i]==b.bk[i]) continue;
			return false;
		}
		return true;
	}
	friend bool operator < (u a,u b){
		for(int i=1;i<=26;i++){
			if(a.bk[i]==b.bk[i]) continue;
			return a.bk[i]<b.bk[i];
		}
		return true;
	}
}s[100005];


map<string,int> p;
map<string,int>::iterator it;
int n;
vector<int> qqq;
long long ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>str;
		s[i].gao();
	}
	//sort(s+1,s+n+1);
	/*for(int i=1;i<=n;i++){
		cout<<s[i].bk<<endl;
	}*/
	for(int i=1;i<=n;i++){
		it=p.find(s[i].bk);
		if(it==p.end()){
			p.insert(make_pair( s[i].bk ,1));
		}
		else p[ s[i].bk ]++;

	}
	it=p.begin();
	while(it!=p.end()){
		int pppp=it->second;
		ans+=pppp*(pppp-1)/2;
		//cout<<it->first<<' '<<it->second<<endl;
		it++;
	}

	cout<<ans;
}

Measured memory_bytes: 19712
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define ll long long
#define ld long double

int main(void)
{
    string n;
    cin >> n;
    ll k = 0;

    for(ll i = 0; i < n.size(); i++) {
        k += n.at(i) - '0';
    }

    if(k % 9)
        cout << "No";
    else
        cout << "Yes";
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const double EPS = 1e-10;
const ll mod=1000000007;
//const ll mod=998244353;
ll a[300010]={};

int main(void){
    ll n;
    cin>>n;
    for(int x=1;x<=100;x++) for(int y=1;y<=100;y++) for(int z=1;z<=100;z++){
        a[x*x+y*y+z*z+x*y+y*z+z*x]++;
    }
    for(int i=1;i<=n;i++) printf("%d\n",a[i]);
}

Measured memory_bytes: 4076
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,i,sum=0,sum1=0;
    cin>>n;
    int a[n+1];
    for (i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
    if (i%2==0) sum+=a[i];
    else sum1+=a[i];
    cout<<sum1-sum<<endl;
    return 0;
}

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

ll bit[300100];

ll n,p[300100],l[300100];

void init(int n){
  for(int i=1;i<=n;i++)bit[i] = 0;
}

ll sum(int i){
  ll res = 0;
  while(i>0){
    res += bit[i];
    i -= i&-i;
  }
  return res;
}

void add(int i,ll val){
  while(i<=n){
    bit[i] += val;
    i += i&-i;
  }
}

int main(){
  cin >> n;
  vector<ll> s(n+1), ss(n+1);

  ss[0] = s[0] = 0;
  for(int i=0;i<n;i++){
    cin >> p[i];
    ss[i+1] = s[i+1] = s[i] + p[i];
  }

  for(int i=0;i<n;i++)cin >> l[i];

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

  for(int i=0;i<n;i++){
    if(ss[i+1]-ss[i]<l[i]){
      cout << -1 << endl;
      return 0;
    }
  }

  n++;  
  ss.erase(unique(ss.begin(),ss.end()), ss.end());
  for(int i=0;i<n;i++){
    s[i] = lower_bound(ss.begin(),ss.end(),s[i]) - ss.begin();
  }

  init(n);
  ll res = 0;

  for(int i=n-1;i>=0;i--){
    res += sum(s[i]+1);
    add(s[i]+1,1);
  }
  
  cout << res << endl;
}

Measured memory_bytes: 7468
#include<iostream>
#include<string>
#include<algorithm>
#define _USE_MATH_DEFINES
#include<math.h>
#include<iomanip>

using namespace std;

int main() {
	double man=0,you=0,tye=0,po3=0;
	int n, i;
	int box1[100] = {};
	int box2[100] = {};

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> box1[i];
	}
	for (i = 0; i < n; i++) {
		cin >> box2[i];
	}
	for (i = 0; i < n; i++) {
		man += fabs(box1[i] - box2[i]);
		if (tye < fabs(box1[i] - box2[i])) {
			tye = fabs(box1[i] - box2[i]);
		}
	}
	for (i = 0; i < n; i++) {
		you += (box1[i] - box2[i]) * (box1[i] - box2[i]);
	}
	
	for (i = 0; i < n; i++) {
		po3 += fabs(box1[i] - box2[i]) * fabs(box1[i] - box2[i]) * fabs(box1[i] - box2[i]);
	}

	cout << fixed << setprecision(6)<<man << endl;
	cout << fixed << setprecision(6) << sqrt(you) << endl;
	cout << fixed << setprecision(6) << pow(po3,1.0/3.0) << endl;
	cout << fixed << setprecision(6) << tye << endl;

	return 0;
}



Measured memory_bytes: 3440
#include<stdio.h>
int main(void) {
	int a, b, k;
	int ans[10000];
	int count = 0;
	//int countb = 0;
	scanf("%d %d %d", &a, &b, &k);
	int x=0 ;
	int flag = 0;
	int count1 = 0;
	if (b <= k) {
		for (int i = a; i <= b; i++) {
			printf("%d\n", i);
		}
		return 0;
	}
	else {
		if (a == b) {
			printf("%d\n", a);
			return 0;
		}
		else {
			for (int i = a; i <=b; i++) {
				count1++;
				if (count1 > k) {
					break;
				}
				ans[count++] = i;
			}
			count1 = 0;
			for (int i = b; i >= a; i--) {
				flag = 0;
				count1++;
				if(count1 > k) {
					break;
				}
				for (int j = 0; j < count; j++) {
					if (ans[j] == i) {
						flag = 1;
						break;
					}
					
				}
				if (flag == 0) {
					ans[count++] = i;
				}
			}
			
			
			int temp;
			for (int i = 0; i < count - 1; i++) {
				for (int j = i + 1; j < count; j++) {
					if (ans[i] > ans[j]) {
						temp = ans[i];
						ans[i] = ans[j];
						ans[j] = temp;
					}
				}

			}
			for (int i = 0; i < count; i++) {
				printf("%d\n", ans[i]);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 128