akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    int n,k;
    cin >> n >> k;
    if(n%k) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 384
h , w = map(int,input().split())
p = []
for i in range(h):
    kar = list(input())
    p.append(kar)
d = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    if i == 0:
        if p[0][0] == "#":
            d[0][0] = 1
    else:
        if p[0][i-1] == "." and p[0][i] == "#":
            d[0][i] += 1
        d[0][i] += d[0][i-1]
for i in range(1,h):
    if p[i-1][0] == "." and p[i][0] == "#":
        d[i][0] += 1
    d[i][0] += d[i-1][0]    

for x in range(1,w):
    for y in range(1,h):
        m = 0
        s = 0
        if p[y][x-1] == "." and p[y][x] == "#":
            m += 1
        m += d[y][x-1]
        if p[y-1][x] == "." and p[y][x] == "#":
            s += 1
        s += d[y-1][x]
        d[y][x] = min(m,s)
print(d[h-1][w-1])

Measured memory_bytes: 3316
n, m = map(int, input().split())
ss = list()
cs = list()
for i in range(m):
    s, c = map(int, input().split())
    ss.append(s)
    cs.append(c)

if n != 1:
    data_range = range(10 ** (n - 1), 10 ** n)
else:
    data_range = range(0, 10)


def is_ok(i):
    for s, c in zip(ss, cs):
        if int(str(i)[s - 1]) != c:
            return False
    return True

for i in data_range:
    if is_ok(i):
        print(i)
        break
else:
    print('-1')


Measured memory_bytes: 3064
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
signed main(){
	int n,e,T;
	cin>>n>>e>>T;
	vi in(n+1);
	rep(i,n)cin>>in[i+1];
	in.pb(e);
	n++;
	vi dp(n+1,inf),dp1(n+1,inf);
	dp[0]=0;
	dp1[0]=-2*in[1];
	int t=1;
	rep(i,n-1){
		while(!(2*(in[i+1]-in[t])<T))t++;
		cmin(dp[i+1],dp[t-1]+T);
		if(t-2>=0)cmin(dp[i+1],dp1[t-2]+2*in[i+1]);
		dp1[i+1]=min(dp[i+1]-2*in[i+2],dp1[i]);
	}
	cout<<in[n]+dp[n-1]<<endl;
}

















Measured memory_bytes: 2544
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int MAX = 200001;
int mult(int a , int b)
{
	return (a * (LL)b) % mod;
}
int add(int a , int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a , int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int modPow(int a , int step)
{
	int ans = 1;
	while(step)
	{
		if(step & 1)
			ans = mult(ans , a);
		step >>= 1;
		a = mult(a , a);
	}
	return ans;
}
vector<int> fact(MAX) , inv(MAX);
int c(int n , int k)
{
	return mult(fact[n] , mult(inv[n - k] , inv[k]));
}
int ways(int h , int w)
{	
	return c(h + w - 2, w - 1);
}
int main()
{	
	int H , W , A , B;
	cin >> H >> W >> A >> B;
	fact[0] = inv[0] = 1;
	for(int i = 1; i < fact.size(); i++)
	{
		fact[i] = mult(fact[i - 1] , i);
		inv[i] = modPow(fact[i] , mod - 2);
	}
	int ans = ways(H , W);
	for(int i = 0; i < B; i++)
	{
		ans = sub(ans , mult(ways(H - A , i + 1) , ways(A , W - i)));
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
        #include <set>
         
        using namespace std;
         
        int main(){
          int a;
          cin>>a;
          
          set<int> values;
          int ans = a;
          int ansv;
          
          for(int i=0; i < 100000000; ++i){
            values.insert(ans);
            if(ans%2==0){
              ans = ans / 2;
            }else{
              ans = 3 * ans + 1;
            }
            if (values.size()!=i+1){
              break;
            }
          }
          cout << values.size() + 1 << endl;
          return 0;
        }

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
 
		char[] sch = s.toCharArray();
		Arrays.sort(sch);
		String s_asc = new String(sch);
 
		char[] tch = t.toCharArray();
		Arrays.sort(tch);
		String t_asc = new String(tch);
		String t_desc = new StringBuilder(t_asc).reverse().toString();
 
		if (s_asc.compareTo(t_desc) < 0)
			System.out.println("Yes");
		else
			System.out.println("No");
		sc.close();
	}
 
}

Measured memory_bytes: 23760
def iskaibun(A):
    if A[0] == A[4] and A[1] == A[3]:
        return True
    else:
        return False

x = list(map(int,input().split()))
s = x[0]
f = x[1]+1
cnt = 0
for i in range(s, f):
    if iskaibun(str(i)):
        cnt += 1
print(str(cnt))

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
	int A, B, C, D,E;
	std::cin >> A >> B;
	C = A + B;
	D = A - B;
	E = A * B;
	int F;
	if (C > D) { 
		if (C > E) {
			std::cout << C;
			return  0; 
		}
		else {
			std::cout << E;
			return 0;
		}
	}
	else if (D > E ){
		cout << D;
	}
	else {
		if ( C > E){
       cout << C;
	   return 0;
		}
		else {
			cout << E;
			return 0;
		}
		
	}

}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] arg) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		ArrayList<String> list = new ArrayList<String>();
		Map<String, Integer> map = new HashMap<String, Integer>();
		for(int i = 0; i < n; i++){
			String s = scan.next();
			if(map.containsKey(s)){
				int v = map.get(s);
				map.put(s, v+1);
			} else {
				map.put(s, 1);
			}

		}
		System.out.println(map.keySet().size());
	}
}


Measured memory_bytes: 77220
#include <bits/stdc++.h>
using namespace std;
int main()
{
  //R,Gを導入
  double R, G;
  int b;
  //入力を求める
  cin >> R >> G;
  //画面にG = (R + b) / 2のときのbを表示
  cout << 2 * G - R << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<complex>
using namespace std;

int main(){
    int r, s, x;
    cin >> r >> s;
    int S = 0;
    int rS;
    int cS[s] = {};
    for (int i=0;i<r;i++){
        rS = 0;
        for (int j=0;j<s;j++){
            cin >> x;
            cout << x << " ";
            S += x;
            rS += x;
            cS[j] += x;
        }
        cout << rS << endl;
    }
    for (int j=0;j<s;j++){
        cout << cS[j] << " ";
    }
    cout << S <<endl;

    return 0;
}

Measured memory_bytes: 3080
"""
implementation of the Insertion Sort
"""
number_of_input = int(raw_input())

numbers = [int(x) for x in raw_input().split()]

for i in range(1, len(numbers)):
    print " ".join([str(x) for x in numbers])
    target = numbers[i]
    index = i - 1
    while index >= 0 and target < numbers[index]:
        numbers[index + 1] = numbers[index]
        index -= 1
    numbers[index + 1] = target

print " ".join([str(x) for x in numbers])

Measured memory_bytes: 6352
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 998244353;

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

  LL A, B, C;
  cin >> A >> B >> C;
  cout << (A%2)*(B%2)*(C%2)*min({A * B, B * C, A * C}) << endl;
}


Measured memory_bytes: 256
public class Main {
	public static void main(String[] args) {
		try (java.util.Scanner sc = new java.util.Scanner(System.in)) {
			while (true) {
				int H = sc.nextInt();
				int W = sc.nextInt();
				if (H == 0 && W == 0) {
					break;
				}

				for (int h = 0; h < H; h++) {
					for (int w = 0; w < W; w++) {
						if ((h + w) %2 == 0) {
							System.out.print("#");
						} else {
							System.out.print(".");
						}
					}
					System.out.println();
				}
				System.out.println();
			}
		}
	}
}


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

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

	int ans = 0;
	for(int i = 1; i <= 9; i++){
		for(int j = 0; j <= 9; j++){
			for(int k = 0; k <= 9; k++){
				int d = 10001*i + 1010*j + 100*k;
				if(a <= d && d <=b)
					ans++;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

   
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        scanner.close();
        int count = 0;
        for(int i = 0 ; i <s.length();i++){
        if(s.charAt(i) == t.charAt(i)){
        count++;
        }
        }
                     System.out.println(count);
    }
    
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
const ll INF = 1001001001;

int main(){
  int n;
  cin >> n;
  rep(i,50000){
    if (int(i*1.08) == n) {
      cout << i <<endl;
      return 0;
    }
  }
  cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int field[6][6][4] = {0},p[3];
	int x,y;
	for(int i=0; i<9; i++){
		if(i%2 == 0){
			for(int j=0; j<4; j++){
				int n;
				scanf("%1d",&n);
				field[j+1][i/2][2] = n;
				field[j+1][i/2+1][0] = n;
			}
		}
		else{
			for(int j=0; j<5; j++){
				int n;
				scanf("%1d",&n);
				field[j][i/2+1][1] = n;
				field[j+1][i/2+1][3] = n;
			}
		}
	}
	p[0] = 1;p[1] = 0; p[2] = 1;
	for(;;){
		if(p[2] == 0){
			if(field[p[0]][p[1]][1] == 1){
				cout<<"U";
				if(field[p[0]][p[1]][0] == 1){p[2] = 3;}
				else{p[1]--;}
			}
			else if(field[p[0]][p[1]][1] == 0){p[2] = 1;p[0]++;}
		}
		else if(p[2] == 1){
			if(field[p[0]][p[1]][2] == 1){
				cout<<"R";
				if(field[p[0]][p[1]][1] == 1){p[2] = 0;}
				else{p[0]++;}
			}
			else if(field[p[0]][p[1]][2] == 0){p[2] = 2;p[1]++;}
		}
		else if(p[2] == 2){
			if(field[p[0]][p[1]][3] == 1){
				cout<<"D";
				if(field[p[0]][p[1]][2] == 1){p[2] = 1;}
				else{p[1]++;}
			}
			else if(field[p[0]][p[1]][3] == 0){p[2] = 3;p[0]--;}
		}
		else if(p[2] == 3){
			if(field[p[0]][p[1]][0] == 1){
				cout<<"L";
				if(field[p[0]][p[1]][3] == 1){p[2] = 2;}
				else{p[0]--;}
			}
			else if(field[p[0]][p[1]][0] == 0){p[2] = 0;p[1]--;}
		}
		if(p[0] == 1 && p[1] == 0){cout <<endl;break;}
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{	
  	string s,t;
  	cin>>s>>t;
  	int n=s.size(),m=t.size();
    int c=INT_MAX;
    for(int i=0;i<=n-m;i++)
    {
        int k=0,p=0;
        for(int j=0;j<m;j++)
        {
            if(s[i+k]!=t[j])
            {
                p++;
                k++;
            }
            else
            {
                k++;
            }
        }
        c=min(c,p);
    }
    cout<<c<<endl;
}

Measured memory_bytes: 3584
N, K = map(int, input().split())
P = list(map(int, input().split()))
p = 0
for j in range(K):
  p += (P[j]+1)/2
m = p
for i in range(N-K):
  p = p + (P[i+K]+1)/2 - (P[i]+1)/2
  m = max(m,p)
print(m)

Measured memory_bytes: 24556
N=int(input())
S=(N*(N+1))//2
A=list(map(int,input().split()))
T=sum(A)
k=T//S
if T%S!=0:
    print("NO")
    exit()
d=[A[i]-A[i-1] for i in range(N)]
for p in [d[i]-k for i in range(N)]:
    if p>0 or p%N!=0:
        print("NO")
        exit()
print("YES")


Measured memory_bytes: 14260
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define PI 3.14159265358979323
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
	FastIO
	dbl a, b;
	dbl x, r;
	cin >> a;
	cin >> b;
	cin >> x;
	if (x <= ((a*a*b)/2))
		r = atan((2*x)/(a*b*b));
	else
		r = atan(a/(2*(b-(x/(a*a)))));
	cout << fixed << setprecision(10) << (90 - ((r*180)/PI));
	return 0;
}

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

int main(){
	int n;
	string s,t;
	cin >> n >> s >> t;
	int sum = 2 * n;
	for(int i = 0; i < n; i++){
		int count = 0;
		if(s[i] == t[0]){
			for(int j = i; j < n; j++){
				if(s[j] != t[count]){
					sum = 2*n;
					break;
				}
				else if(j == n - 1){
					sum -= (n - i);
				}
				count++;
			}
		}
		if(sum != 2 * n){
			break;
		}
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
a = [int(input()) for _ in range(N)]

i = 0
cnt = 1
while True:
    if cnt > len(a):
        cnt = -1
        break
    if a[i] == 1:
        cnt = -1
        break
    elif a[i] == 2:
        break
    else:
        i = a[i] - 1
        cnt += 1
print(cnt)


Measured memory_bytes: 7084
import sys
sys.setrecursionlimit(500000)

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    print(((N+1000-1)//1000)*1000-N)


if __name__ == '__main__':
    main()


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

int main()
{
	int a,b;

	cin>>a>>b;
	
	if(b==1)
	{
		cout<<0<<"\n";
		return 0;
	}

	int ans = (b-1)/(a-1);

	ans += ((b-1)%(a-1)?1:0);

	

	cout<<ans<<"\n";

	return 0;
}

Measured memory_bytes: 384
N, X = map(int, input().split())

counts = [0] * (N+1)
counts[0] = 1
for i in range(1, N+1):
    counts[i] = 2 * counts[i-1] + 3


def req(n, x):
    if n == 0:
        return 1

    if x == 1:
        return 0
    elif x > 1 and x <= counts[n-1] + 1:
        return req(n - 1, x - 1)
    elif x == counts[n-1] + 2:
        return req(n - 1, counts[n-1]) + 1
    else:
        if x == 2*counts[n-1] + 3:
            return req(n-1, counts[n-1]) * 2 + 1
        else:
            return req(n-1, x - (counts[n-1] + 2)) + req(n - 1, counts[n-1]) + 1


print(req(N, X))


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


int main(){
  int n;cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  for(int i = 0; n > i; i++){
    cin>>a[i];
    b[i] = a[i];
  }
  sort(b.begin(),b.end());
  //n/2 , n/2+1
  for(int i = 0; n > i; i++){
    if(a[i] <= b[n/2-1]){
    
      cout << b[n/2] << endl;
    }else{
      cout << b[n/2-1] << endl;
    }
  }
  
}

Measured memory_bytes: 3712
def main():
    s=int(input())
    h=s//100
    t=s%100
    yymm=False
    mmyy=False
    if 1<=t<=12:
        yymm=True
    if 1<=h<=12:
        mmyy=True
    if yymm == True and mmyy == True:
        print('AMBIGUOUS')
    elif yymm == mmyy:
        print('NA')
    elif yymm == True:
        print('YYMM')
    else:
        print('MMYY')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Ord

main :: IO ()
main = getLine >> readLine >>= printRes . solve
    where
        printRes = putStrLn . unwords . map show

-- |
-- >>> solve [6, 9, 4, 2, 11]
-- [11,6]
-- >>> solve [100, 0]
-- [100,0]
solve :: [Int] -> [Int]
solve = check . sortBy (flip compare)
    where
        check (x : xs) = [x, head $ sortBy cmpf xs]
            where
                hx = x `div` 2
                cmpf = comparing (abs . (hx -))


readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 16636
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<ll> VLL;
typedef vector<PLL> VP;
const static int INF = 1000000000;
const static int MOD = 1000000007;
const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "
//charを整数に
int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; }
// 累積和 for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; 
void cum_sum(int N,vector<double> a, vector<double> &s){ for(int i=0; i<N; i++){ s[i+1]=s[i]+a[i];}}
//ユークリッドの控除法
ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
//最小公倍数
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}
//素数判定
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
int getdigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
//空白文字も入力 getline(cin, S);
//桁数指定 setprecision

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    ll N;
    cin >> N;
    VLL a(N);
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    VLL ball(N);
    ll count=0;
    for(int i=N-1; i>=0; i--){
        ll sum=0;
        for(int j=i+1; j<=N; j+=(i+1)){
            sum+=ball[j-1];  
        }
        if(sum%2!=a[i]){
            if((sum+1)%2==a[i]){
                ball[i]=1;
                count++;
            }
            else{
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << count << endl;
    rep(i,N){
        if(ball[i]==1){
            cout << i+1 << endl;
        }
    }
}

Measured memory_bytes: 6296
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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 ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

template <int mod>
struct ModInt {
    int val;
    ModInt() : val(0) {}
    ModInt(long long x) : val(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    int getmod() { return mod; }
    ModInt &operator+=(const ModInt &p) {
        if ((val += p.val) >= mod) {
            val -= mod;
        }
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if ((val += mod - p.val) >= mod) {
            val -= mod;
        }
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        val = (int)(1LL * val * p.val % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }
    ModInt operator-() const { return ModInt(-val); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return val == p.val; }
    bool operator!=(const ModInt &p) const { return val != p.val; }
    ModInt inverse() const {
        int a = val, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n) const {
        ModInt ret(1), mul(val);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.val; }
    friend istream &operator>>(istream &is, ModInt &a) {
        long long t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }
    static int get_mod() { return mod; }
};
const int MOD = 998244353;  // if inv is needed, this shold be prime.
using modint = ModInt<MOD>;

modint dp[3005][6005];
int main() {
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }

    for (int i = 0; i < N; i++) {
        dp[i][0] += 1;
        for (int s = 0; s <= S; s++) {
            dp[i + 1][s] += dp[i][s];
            dp[i + 1][s + A[i]] += dp[i][s];
        }
    }
    modint ans(0);
    for (int i = 0; i < N; i++) {
        ans += dp[i + 1][S];
    }

    cout << ans << endl;
}


Measured memory_bytes: 70784
from operator import itemgetter
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
infi=10**9
dp=[infi]*2*10**4
dp[0]=0
for a,b in ab:
  for i in range(h):
    if dp[i]!=infi:
      dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

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

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

int main() {
  string s;
  cin >> s;
  int ans = 0;
  rep(i, 3) {
    if (s[i] == '1') {
      ans++;
    }
  }
  cout << ans << endl;
}

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

int main() {
	ll const MOD = 1000000007;
	int n;
	cin >> n;
	vector<vector<int> > a(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> a[i][j];
		}
	}

	vector<ll> dp(1<<n, 0);
	dp[0] = 1;

	for (int i = 0; i < n; ++i)
	{
		for (ll j = 0; j < 1<<n; ++j)
		{
			if (__builtin_popcountll(j)!=i) continue;
			for (int k = 0; k < n; ++k)
			{
				if (a[i][k]==1 && (j>>k)%2==0)
				{
					dp[j+(1<<k)] = (dp[j+(1<<k)] + dp[j]) % MOD;
				}
			}
		}
	}
	cout << dp[(1<<n)-1] << "\n";
	return 0;
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
#pragma push_macro("long")
#undef long
#ifdef _WIN32
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; }
inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); }
#endif // _WIN32
#pragma pop_macro("long")
#endif // _MSC_VER
/*---------------------------------------------------------------------------------------------------
????????????????????????????????? ??§?????§  
??????????????? ??§?????§ ???????´<_??? ?????? Welcome to My Coding Space!
???????????? ??? ?´_???`??????/??? ???i     
?????????????????????????????? ???  |???|     
????????? /?????? /??£??£??£??£/??????|  
??? ???_(__??????/???    ???/ .| .|????????????  
??? ????????????/????????????/??????u??????  
---------------------------------------------------------------------------------------------------*/
 


int M, X[20], Y[20];
int dp1[1 << 16];
set<pair<int, int>> dp2[1 << 16];
int dp3[1 << 16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> M;
    rep(i, 0, M) cin >> X[i] >> Y[i];

    dp1[0] = 1;
    rep(a, 0, M) rep(b, a + 1, M) {
        int msk = (1 << a) + (1 << b);
        dp1[msk] = 1;
        dp2[msk].insert({X[b] - X[a], Y[b] - Y[a]});
    }

    rep(msk, 0, 1 << M) {
        if (__builtin_popcount(msk) % 2 == 1) continue;
        if (__builtin_popcount(msk) <= 3) continue;
        rep(a, 0, M) if (msk & (1 << a)) rep(b, a + 1, M) if (msk & (1 << b)) {
            int nmsk = msk - (1 << a) - (1 << b);
            if (!dp1[nmsk]) continue;
            
            int dx = X[a] - X[b];
            int dy = Y[a] - Y[b];

            fore(p, dp2[nmsk]) {
                if (dx * p.second == dy * p.first) {
                    dp1[msk] = 1;
                    dp2[msk].insert(p);
                }
            }
        }
    }

    rep(msk, 0, 1 << M) if(dp1[msk]) {
        int c = __builtin_popcount(msk)/ 2;
        dp3[msk] = c * (c - 1) / 2;
    }

    rep(msk, 0, 1 << M) {
        for (int i = msk; i >= 0; i--) {
            i &= msk;

            dp3[msk] = max(dp3[msk], dp3[i] + dp3[msk - i]);
        }
    }

    int ans = dp3[(1 << M) - 1];
    cout << ans << endl;
}

Measured memory_bytes: 6640
from collections import Counter

n = int(input())

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

factor = prime_factor(n)
c = Counter(factor)

cnt = 0
for k, v in c.items():
    num, idx = 1, 1
    while num <= v:
        cnt += 1
        idx += 1
        num += idx

print(cnt)

Measured memory_bytes: 66292
//Apparat : drobucs, aleonov, vit_72
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <iomanip>
#include <algorithm>
#include <string>
#include <queue>
#include <numeric>

//#pragma warning(disable : 4996)
//#pragma GCC optimize("O3")

using namespace std;

#define nptr nullptr
#define all(x) (x).begin(), (x).end()
#define drobucs ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()

typedef  long long ll;

const int maxn = (int)1e7 + 13;
const ll INFL = 9223372036854775807;
const ll INF = 2147483647;
const ll MOD = (int)1e9 + 7, MOD2 = 998244353;//1e9 + 21, 1e9 + 33, 1e9 + 87, 1e9 + 93
const ll base = 101, base2 = 37;

int main() {
	drobucs;

	int n;
	cin >> n;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; ++i)cin >> v[i].ff >> v[i].ss;
	sort(all(v));
	if (n & 1) {
		int l = 0, r = 0;
		l = v[n / 2].ff;
		sort(all(v), [](pair<int, int> a, pair<int, int> b) {return a.second > b.second; });
		r = v[n / 2].ss;
		cout << r - l + 1 << "\n";
	}
	else {
		int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
		l2 = v[n / 2].ff;
		l1 = v[n / 2 - 1].ff;
		sort(all(v), [](pair<int, int> a, pair<int, int> b) {return a.second < b.second; });
		r1 = v[n / 2].ss;
		r2 = v[n / 2 - 1].ss;
		cout << r1 + r2 - l1 - l2 + 1 << "\n";
	}
	return 0;
}

Measured memory_bytes: 4780
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

H1, M1, H2, M2, K = MAP()

print(max(0, 60*H2+M2-60*H1-M1-K))

Measured memory_bytes: 9984
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func stringLineScan() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(stringLineScan())
	a := make([]int, n)
	d := 1000000007
	for i := 0; i < n; i++ {
		t, _ := strconv.Atoi(stringLineScan())
		a[t]++
	}
	if n%2 == 0 {
		ans := 1
		for i := 1; i < n; i += 2 {
			if a[i] == 2 {
				ans *= 2
				ans %= d
			} else {
				ans = 0
				break
			}
		}
		fmt.Println(ans)
	} else {
		ans := 1
		if a[0] == 1 {
			for i := 2; i < n; i += 2 {
				if a[i] == 2 {
					ans *= 2
					ans %= d
				} else {
					ans = 0
					break
				}
			}
			fmt.Println(ans)
		} else {
			fmt.Println(0)
		}
	}
}


Measured memory_bytes: 2048
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<cmath>
using namespace std;
using Graph = vector<vector<int>>;
typedef unsigned long long ll;
ll mod = (10e+8)+ 7;

#define For(N,i) for(int i = 0; i < N; i++)
	
int main(){
	int N;
	cin>>N;
	unordered_map<int,int> num;
	for(int i = 0; i < N; i++){
		int a;
		cin>>a;
		num[a]=i;
	}
	for(int i = 1; i <= N; i++){
		
				cout<<num[i]+1<<" ";
		
	}
	cout<<endl;
}

Measured memory_bytes: 4900
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#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 eb emplace_back

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main(){
	int r;
	cin >> r;
	int score[] = {1200, 2800, 10000};
	string title[] = {"ABC", "ARC", "AGC"};
	rep(i,3) {
		if(r < score[i]){
			cout << title[i] << endl;
			return;
		}     
	}
	return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数


int main()
{
  int r, g, b, n ;
  cin >> r >> g >> b >> n ;
  
  int rp = n/r ;
  int gp = n/g ;
  int bp = n/b ;
  int hoge ;
  
  int cnt = 0 ;
  
  int left, right, mid ;
  
  REP(i,rp+1){
    REP(j,gp+1){
      hoge = n-(i*r+j*g) ;
      left = 0 ;
      right = bp+1 ;
      while(left<right){
        mid = (left+right)/2 ;
        if(mid*b==hoge){
          cnt++ ;
          break ;
        }
        else if(hoge<mid*b){
          right = mid ;
        }
        else{
          left = mid+1 ;
        }
      }
    }
  }
          
  
  cout << cnt <<endl ;
    


  return 0 ;
}



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

int main() {
  string S;
  cin >> S;
  int n1 = atoi(S.substr(0,2).c_str());
  int n2 = atoi(S.substr(2,4).c_str());

  if (0 < n1 && n1 <= 12) {
    if (0 < n2 && n2 <= 12) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;
    }
  } else {
    if (0 < n2 && n2 <= 12) {
      cout << "YYMM" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
}

Measured memory_bytes: 888
#include <iostream>

using namespace std;

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

   if (a>x){
    cout<<"NO";
   }

 else  if(a<=x && a+b>=x){
    cout<<"YES";
   }
   else {
    cout<<"NO";
   }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
    is>>p.first>>p.second; return is; }
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 <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int H,W;
    cin>>H>>W;
    vector<vector<int>> c(10,vector<int>(10));
    cin>>c;
    
    REP(i,10) REP(j,10) REP(k,10) chmin(c[j][k],c[j][i]+c[i][k]);

    vector<int> cnt(10);
    REP(i,H) {
        REP(j,W) {
            int t;
            cin>>t;
            if(t!=-1) {
                cnt[t]++;
            }
        }
    }
    int ans=0;
    REP(i,10) {
        ans+=c[i][1]*cnt[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int main(){
	int n,x;
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++)
	    scanf("%d",&a[i]);
	int ans=0;
	sort(a,a+n);
	for(int i=0;i<n;i++)
	    if(a[i]<=x){
	    	ans++;
	    	x-=a[i];
		}
		else{
			x=0;
			break;
		}
	if(x)
	    ans--;
	printf("%d\n",ans);
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main() {
    ll N, K; cin >> N >> K;
    vl A(N);
    rep(i,N) cin >> A[i];
    sort(all(A));

    ll ng = 2e18, ok = -ng;
    while (ng - ok > 1) {
        ll x = (ok + ng) / 2, cnt = 0;
        rep(i,N) {
            if (A[i] < 0) {
                cnt += N - (upper_bound(all(A), (long double)x/A[i]) - A.begin());
            } else if (A[i] > 0) {
                cnt += lower_bound(all(A), (long double)x/A[i]) - A.begin();
            } else if (x > 0) cnt += N;
            if (A[i]*A[i] < x) cnt--;
        }
        (cnt/2 < K ? ok : ng) = x;
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define hi ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define pb push_back
#define emb emplace_back
#define mp make_pair
#define srt(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define reverse(a) reverse(a.begin(), a.end())
#define F first
#define S second
#define pii pair<int, int>
#define vi vector<int>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define de(x) cout << #x << " is " << x << '\n'
typedef long long ll;
using namespace std;
int main()
{
    hi;
    int n, a;
    cin >> n;
    set<int> se;
    vector<int> res;
    rep(i, 0, n)
    {
        cin >> a;
        if (se.count(a))
        {
            se.erase(a);
            res.pb(a);
        }
        else
            se.insert(a);
    }
    rsort(res);
    if (res.size() >= 2)
    {
        cout << (ll)res[0] * (ll)res[1] << '\n';
    }
    else
        cout << 0;
    return 0;
}


Measured memory_bytes: 4992
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static double xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2;
	
	public static void main(String[] args){
		while(read()){
			slove();
		}
	}
	static boolean read(){
		if(sc.hasNext() == false)
			return false;
		xa1 = sc.nextDouble();
		ya1 = sc.nextDouble();
		xa2 = sc.nextDouble();
		ya2 = sc.nextDouble();
		xb1 = sc.nextDouble();
		yb1 = sc.nextDouble();
		xb2 = sc.nextDouble();
		yb2 = sc.nextDouble();
		return true;
	}
	static void slove(){
		if(yb1 > ya2){
			System.out.println("NO");
		}else if(xb2 <xa1){
			System.out.println("NO");
		}else if(ya1 > yb2){
			System.out.println("NO");
		}else if(xb1 > xa2){
			System.out.println("NO");
		}else{
			System.out.println("YES");
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int n,k,arr[100005];
int func(int i)
{

    if(i<=1) return 0;
    if(dp[i]!=-1) return dp[i];
    int ans=1e9;
    for(int j=1;j<=k;j++){
        if(i-j>=1){
            ans = min(ans,func(i-j)+abs(arr[i]-arr[i-j]));
        }
        dp[i]=ans;
    }
    return dp[i];
}
int main()
{
    int i;
    cin>>n>>k;

    for(i=1;i<=n;i++) cin>>arr[i];
    memset(dp,-1,sizeof dp);
    int ans = func(n);
    cout<<ans;
}



Measured memory_bytes: 5760
D, G = map(int, input().split())
G //= 100
P = [] 
C = []
for i in range(1, D+1):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c//100)

scores = []
nums = []
for i in range(0, 2**D):
    score = 0
    num = 0
    remain = []
    for j in range(D):
        if (i>>j)&1:
            score += P[j]*(j+1) + C[j]
            num += P[j]
        else:
            remain.append(j)
    if score >= G:
        scores.append(score)
        nums.append(num)
    else:
        remain = sorted(remain, reverse=True)
        nokori = G - score
        for r in remain:
            if P[r] > -(-nokori // (r+1)):
                num += -(-nokori // (r+1))
                nums.append(num)
                break
print(min(nums))

Measured memory_bytes: 3064
import sys

a = list(map(int,input().split()))
N = a[0]
Y = a[1]
flg = 0
for i in range(N+1):
    remain = N - i
    for j in range(remain + 1):
        if 10000*i + 5000*j + 1000*(remain - j) == Y:
            print(str(i) + " " + str(j) + " " + str(remain-j))
            sys.exit()
print("-1 -1 -1")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC113C - ID
  // N個の県があり、合わせてM個の市が属している
  // Yi年に誕生、Pi県に属している、同じ年に誕生した市は複数存在しない
  // 市に12桁の認識番号を振る
  // 上6桁はPi、下6桁はx（xはPi県に属する市でx番目に誕生した）
  // 市が1つも属さない県がある
  int N, M; cin >> N >> M; // N:県の数、M:市の数
  vector<vector<int> > ans(M, vector<int>(2, 0));
  // 掲載の順番(項番)を保持する配列、[項番(M個)][0:県番号,1:市の誕生順]
  vector<vector<pair<int, int> > > p(N, vector<pair<int, int> >());
  // 各県の情報を保持、[県番号(N個)][{年、項番}のペア……]を入れていく
  // ペアをsortして、順番をansに入れる
  REP(i, M){
    int P, Y; cin >> P >> Y; P--; // Pについて0-indexed
    ans[i][0] = P; // i番目に県の情報を入れる
    p[P].push_back({Y, i}); // 県番号のところにペアを入れる
  }
  REP(i, N){ // sortするために県ごとに見ていく
    sort(p[i].begin(), p[i].end()); // 県の中でsortする
    REP(j, p[i].size()){
      ans[p[i][j].second][1] = j + 1; // sortした順番の情報をansに入れる
    }
  }
  REP(i, M){
    cout << setfill('0') << setw(6) << ans[i][0] + 1;
    cout << setfill('0') << setw(6) << ans[i][1] << endl;
  }
}


Measured memory_bytes: 12416
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
const ll  MAX_V=20000;
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}

//辺の構造体　
struct edge{
    //行き先、容量、逆辺の場所
    ll to,cap,rev;
};
//グラフの隣接リスト
vector<vector<edge>> G(MAX_V);
//DFSで調べた頂点を記録
bool used[MAX_V];

//辺の情報を代入する関数
void add_edge(ll from,ll to,ll cap){
    G[from].push_back(edge{to,cap,(ll)G[to].size()});
    G[to].push_back(edge{from,0,(ll)G[from].size()-1});
}
//増加パスをDFSで探す
ll dfs(ll v,ll t,ll f){
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        edge &e=G[v][i]; //辺の容量を更新するためのアドレス
        if(!used[e.to]&&e.cap>0){
            ll d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;//使った分減らす
                G[e.to][e.rev].cap+=d;//使った分逆辺の容量を増やす
                return d;
            }
        }
    }
    return 0;
}
//sからtへの最大流を求める
ll max_flow(ll s,ll t){
   ll flow=0;
   while(1){
       for(int i=0;i<MAX_V;i++)used[i]=false;
       ll f=dfs(s,t,inf);
       if(f==0)return flow;
       flow+=f;
   }
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;cin>>n;
vector<ll> a(n),b(n),c(n),d(n);
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
for(int i=0;i<n;i++)cin>>c[i]>>d[i];
for(int i=0;i<n;i++){
		add_edge(2*n,i,1);
	}
	for(int i=0;i<n;i++){
		add_edge(n+i,2*n+1,1);
	}
 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i]<c[j]&&b[i]<d[j])add_edge(i,n+j,1);
		}
	}
	cout << max_flow(2*n,2*n+1) << endl;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>

#define ran 202202

int n, m, L;
int x, y;
char a[ran], b[ran];
int fa[ran], fb[ran];

bool calc(int st, int lim) {
	int l = 1, r = lim;
	for(int i=L-1; i>=0; i--) {
		if(fb[i]==1 && l>1) l--;
		if(fb[i]==-1 && r<lim) r++;
		
		if(fa[i]==-1) l++;
		if(fa[i]==1) r--;
		if (l>r) return false;
	}
	return l<=st && st<=r;
}

int main() {
	scanf("%d%d%d", &n, &m, &L);
	scanf("%d%d", &x, &y);
	scanf("%s%s", a, b);
	
	bool ans = true;
	
	memset(fa, 0, sizeof fa);
	memset(fb, 0, sizeof fb);
	for(int i=0;i<L;i++) {
		if(a[i]=='U') fa[i] = -1;
		if(a[i]=='D') fa[i] = 1;
		if(b[i]=='U') fb[i] = -1;
		if(b[i]=='D') fb[i] = 1;
	}
	ans &= calc(x, n);
	
	memset(fa, 0, sizeof fa);
	memset(fb, 0, sizeof fb);
	for(int i=0;i<L;i++) {
		if(a[i]=='L') fa[i] = -1;
		if(a[i]=='R') fa[i] = 1;
		if(b[i]=='L') fb[i] = -1;
		if(b[i]=='R') fb[i] = 1;
	}
	ans &= calc(y, m);
	
	puts(ans ? "YES" : "NO");
	
	return 0;
}

Measured memory_bytes: 2176
import sys
readline = sys.stdin.readline
from collections import Counter

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    c = Counter(A)
    for key, val in c.items():
        if val > 2:
            if val % 2 == 0:
                c[key] = 2
            else:
                c[key] = 1
    
    if len([val for key, val in c.items() if c[key] == 2]) % 2 == 0:
        print(len(c))
    else:
        print(len(c) - 1)


if __name__ == '__main__':
    main()

Measured memory_bytes: 18648
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int[] a = new int[N];
            for (int i = 0; i < N; i++) {
                a[i] = in.nextInt() - 1;
            }

            int current = 0;
            for (int i = 1; i <= N; i++) {
                current = a[current];
                if (current == 1) {
                    System.out.println(i);
                    return;
                }
            }

            System.out.println(-1);
        }
    }
}


Measured memory_bytes: 49564
def resolve():
    X = int(input())
    if 400 <= X <= 599:
        print(8)
    if 600 <= X <= 799:
        print(7)
    if 800 <= X <= 999:
        print(6)
    if 1000 <= X <= 1199:
        print(5)
    if 1200 <= X <= 1399:
        print(4)
    if 1400 <= X <= 1599:
        print(3)
    if 1600 <= X <= 1799:
        print(2)
    if 1800 <= X <= 1999:
        print(1)
    return
resolve()

Measured memory_bytes: 9192
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll a[100010];

int main() {
	int N;
	cin >> N;
	for(int i=0; i<N; ++i) cin >> a[i];
	ll ans=0;
	for(int d=59; d>=0; --d){
		ll t=((ll) 1<<d);
		int cnt=0;
		for(int i=0; i<N; ++i){
			if((a[i])&t) ++cnt;
		}
		if(cnt%2==1){
			ans += t;
			for(int i=0; i<N; ++i){
				if((a[i])&t) a[i] -= t;
			}
		}
	}
	int now=0;
	for(int d=59; d>=0; --d){
		ll t=((ll) 1<<d);
		for(int i=now; i<N; ++i){
			if((a[i])&t){
				swap(a[now], a[i]);
				for(int j=0; j<N; ++j){
					if(j!=now && (a[j])&t){
						a[j] ^= a[now];
					}
				}
				++now;
				break;
			}
		}
		int px=0;
		for(int i=0; i<N; ++i){
			if((a[i])&t) ++px;
		}
		if(px%2==1){
			ans += t*2;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024