akhauriyash/Code-Regression huggingface dataset:
//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    string s; cin >> s;
    bool ok = true;
    for(size_t i = 0; i < s.size(); i++){
        auto& c = s[i];
        if(i & 1){
            ok &= c != 'R';
        }else{
            ok &= c != 'L';
        }
    }
    cout << (ok ? "Yes" : "No") << '\n';
}


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

int main(){
  int64_t N;
  cin>>N;
  int64_t ans=0;
  
  if(N%2!=0){
    ans=0;
  }
  else{
    int64_t M=N/2;
    while(M>=1){
      ans += M/5;
      M=M/5;
    }
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 200005;

ll a[MAX_N];
int n;

bool possible(ll cri)
{
	ll asum[3];
	asum[0] = asum[1] = asum[2] = 0;
	int r=0;
	int rr[2];
	int i=0;
	rep(i,2){
		while(asum[i] < cri && r<n){
			asum[i] += a[r];
			r++;
		}
		if(r>=n){
			break;
		}
		rr[i] = r;
	}
	if(r>=n&&i==0){
		return false;
	}
	for(;r<n;r++){
		asum[2] += a[r];
	}
	if(asum[2] >= cri){
		return true;
	}
	rep(i,n){
		asum[0] -= a[i];
		rep(j,2){
			r = rr[j];
			while(asum[j] < cri && r<n+i+1){
				asum[j] += a[r];
				asum[j+1] -= a[r];
				r++;
			}
			if(r>n+i){
				break;
			}
			rr[j] = r;
		}
		if(r<n+i+1){
			asum[2] += a[n+i];
		}
		if(asum[2] >= cri){
			return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d",&n);
	rep(i,n){
		scanf("%lld",&a[i]);
		a[i+n] = a[i];
	}
	ll asum = accumulate(a,a+n,0LL);
	ll amin = *(min_element(a,a+n));
	ll h=asum/3+1;
	ll l=amin-1;
	ll ans;
	while(1){
		ll mid = (l+h)/2;
		if(l==mid){
			ans = mid;
			break;
		}
		if(possible(mid)){
			l = mid;
		}else{
			h = mid;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main()
{
    cin >> K;
    ll tmp = 7 % K;
    rep(i, K + 1)
    {
        if (tmp % K == 0)
        {
            cout << i + 1 << endl;
            return 0;
        }
        tmp = (tmp * 10 + 7) % K;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld  long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, dp[1000002][2][2], mod=1e9+7;
int solve(int i, int g1, int g2)
{
    if(i==n)
        return (g1&&g2);
    int &ans=dp[i][g1][g2];
    if(ans!=-1)
        return ans;
    ans=8LL*solve(i+1,g1,g2)%mod;
    ans=(1LL*ans+solve(i+1,1,g2))%mod;
    ans=(1LL*ans+solve(i+1,g1,1))%mod;
    return ans;
}
int main()
{
    IO
    cin>>n;
    memset(dp,-1,sizeof dp);
    cout<<solve(0,0,0);
}


Measured memory_bytes: 81692
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_f(const void *a, const void *b) {
	return *((int64_t *)a) < *((int64_t *)b) ? -1 : 1;
}

int compare_f2(const void *a, const void *b) {
	return *((uint64_t *)a) > *((uint64_t *)b) ? -1 : 1;
}

static size_t comb(const size_t n, const size_t r) {
	size_t result = 1;

	for (size_t i = 0; i < r; i++) {
		result *= n - i;
		result /= i + 1;
	}

	return result;
}

static uint64_t gcd(uint64_t m, uint64_t n)
{
	uint64_t temp;

	while (m%n != 0) {
		temp = n;
		n = m % n;
		m = temp;
	}

	return n;
}

static int64_t X[100000];
static uint64_t diff[100000];

int main(void) {
	size_t N, M;

	scanf("%zu %zu\n", &N, &M);
	for (size_t i = 0; i < M; i++) {
		scanf("%"PRId64, &(X[i]));
		if (i < M - 1) {
			scanf(" ");
		}
	}

	if (M <= N){
		printf("%d", 0);
	}
	else {
		qsort(X, M, sizeof(int64_t), compare_f);

		for (size_t i = 0; i < M - 1; i++) {
			diff[i] = (uint64_t)(X[i + 1] - X[i]);
		}

		qsort(diff, M - 1, sizeof(uint64_t), compare_f2);

		uint64_t sum = 0;

		for (size_t i = 0; i < N - 1; i++) {
			sum += diff[i];
		}

		printf("%"PRIu64, (uint64_t)(X[M - 1] - X[0]) - sum);
	}

	return 0;
}


Measured memory_bytes: 2540
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        List<Integer> p = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            p.add(sc.nextInt());
        }
        Collections.sort(p);

        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += p.get(i);
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 30352
#include <stdio.h>
#include <algorithm>
using namespace std;

int a[2222];

int main(void)
{
	int n, i, j, ans = 0;

	scanf("%d" ,&n);
	for (i = 1; i <= n; i++)
		scanf("%d" ,&a[i]);

	sort(a + 1, a + n + 1);

	for (i = 1; i <= n; i++)
		for (j = i + 1; j <= n; j++)
		{
			int point = upper_bound(a + j, a + n + 1, a[i] + a[j] - 1) - 1 - a;
			ans += point - j;
		}

	printf("%d" ,ans);
	return 0;
}

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


int main() {
    int N, x;
    cin >> N >> x;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a.at(i);
    }

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

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (i < N-1 && x >= a.at(i)) {
            x -= a.at(i);
            ans++;
        } else if (i == N-1 && x == a.at(i)) {
            ans++;
        } else {
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for(int i = 0; i < k; i++)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }
    for(int bit = 0; bit < (1<<k); bit++)
    {
        int val = 0;
        vector<int> w;
        for(int i = 0; i < k; i++)
        {
            if(bit & (1<<i))
            {
                val |= (1<<v[i]);
                w.push_back(v[i]);
            }
        }
        cout << val << ":";
        for(int i = 0; i < w.size(); i++) cout << " " << w[i];
        cout << endl;
    }
    return 0;
}




Measured memory_bytes: 3212
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string>


using namespace std;

int main(void)
{
	string a, b, c;
	cin >> a >> b >> c;
	int n = b.length();
	cout << "A" << b[0]<< "C" << endl;
	return 0;
}


Measured memory_bytes: 256
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define pb          push_back
#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 jell        998244353
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define DEC(N)  cout << std::fixed; cout << setprecision(N);
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
  // cin>>t;
    for(int ok=1;ok<=t;ok++)
    {
       string s;
       cin>>s;
       if(s=="ABC")
       	cout<<"ARC";
       else
       	cout<<"ABC";
       cout<<endl;
     
    }
    return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  vector<ll> sum(N+1, 0);
  REP(i, N){
    cin >> A[i];
  }
  map<int, int> mp;
  mp[0]++;
  REP(i, N){
    sum[i+1] = sum[i] + A[i];
    sum[i+1] %= M;
    mp[sum[i+1]]++;
  }
  ll ans = 0;
  for(auto pr : mp){
    ans += (ll)pr.second * (pr.second-1)/2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4352
# -*- coding: utf-8 -*-
import math

a = int(input()) #500
b = int(input()) #100
c = int(input()) #50
x = int(input()) #target

res = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            total = 500*i + 100*j + 50*k
            if x == total:
                res += 1
print(res)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )

using namespace std;
using ll = long long;
using P = pair<int,int>;
int main()
{
    int n;
    cin>>n;
    bool ok = true;
    for(int i = 0 ; i<n&&ok ; i++)
    {
        int x; cin>>x;
        if(x%2==0)
        {
            if(!(x%3==0 || x%5==0))
            {
                ok = false;
            }
        }

    }
    if(ok)
    {
        cout<<"APPROVED"<<endl;
    }
    else
    {
        cout<<"DENIED"<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <functional>
#include <string>
using namespace std;


int main() {
	string s;
	cin >> s;
	long b = 0, c = 0;
	for (size_t l = 0; l < s.length(); l++) {
		if (s[l] == 'W') {
			c += l - b;
			b++;
		}
	}
	cout << c << endl;

	return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


 
int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
#endif
	
	string s, t;
	cin >> s;
	cin >> t;
	cout << t;
	cout << s << '\n';
		
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 256
inf=10**10
n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(n)]
memo=[[inf]*401 for _ in range(401)]
memo[0][0]=0
for a,b,c in abc:
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if memo[i][j]!= inf :
        memo[i+a][j+b]= min(memo[i+a][j+b], memo[i][j] + c)


ans=inf
for i in range(1,min(400//ma,400//mb)):
  ans=min(ans, memo[ma*i][mb*i])

if ans==inf:
  print(-1)
else:
  print(ans)

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

using namespace std; 

int main(){ 
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(k-a[i]<a[i]){
      ans+=(k-a[i])*2;
    }
    else {
      ans+=a[i]*2;
    }
  }
  cout<<ans;
}

 

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;//1000000000 + 7 998244353 924844033 1000000000 + 9;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<double, double> Dll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge {
	LL from, to, cost;
};
vector<vector<LL>>g;
vector<edge>ed;
vector<Pll>pv;
map<string, LL>ma;
set<LL>st;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
LL n, m,k, p, q, w, h, ans, cnt, dp[2000][2000], sum, a[200000], b[200000];
string str[10000];
bool f;
char c[1100][1100];
int main() {
	cin >> n;
	LL pre = 2;
	while (pre<=n) {
		LL l = pre, r = n+1, mid;
		while (r - l > 1) {
			mid = (l + r) / 2;
			if (n / pre > n / mid)
				r = mid;
			else l = mid;
		}
		LL cur = n % pre, num = n / pre;
		if(num==n%(pre + (cur / num - 1)))
			ans += (pre + (cur / num - 1));
		//cout<<cur - (cur / num - 1)*num << " " <<  (pre + (cur / num - 1)) << endl;
			pre=l+1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 512
H, W =map(int, input().split())
ans =0
if H ==1 or W ==1:
    ans = 1
elif H %2 ==0:
    ans =0
    ans = (H *W )//2
else:
    ans =0
    ans = ((H-1) * W)//2
    ans += (W+1)//2
print(int(ans))

Measured memory_bytes: 3060
//Date : 07 - 07 -18 //Author : Rishabh Paul

#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
char s[N];
int main() {
	int n ,w;
	scanf("%s" ,s);
	fflush(stdin);
	scanf(" %d" ,&w);
	n = strlen(s);
	for(int i = 0 ; i < n ; i+=w)	printf("%c" ,s[i]);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int count = 0;
		for(int i = 0; i < s.length(); i++){
			if(s.charAt(i) == '1'){
				count++;
			}
		}
		System.out.println(count);
    }
}

Measured memory_bytes: 21844
def sum_ketagoto(n):
    nsum = 0
    while n != 0:
        nsum += n % 10
        n //= 10
    return nsum


def main():
    n, a, b = map(int, input().split())
    nsum = 0
    for j, k in zip(map(lambda i: sum_ketagoto(i), range(1, n + 1)), range(1, n + 1)):
        if a <= j and j <= b:
            nsum += k
    print(nsum)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#define ll long long

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int n,v;
int a[2010];
bitset<(int)4e6+10> dp;

int main(int argc, char** argv) {
	int i,j;
	int sum=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	dp=0;dp[0]=1;
	for(i=1;i<=n;i++)
		dp|=dp<<a[i];
	for(i=(sum+1)/2;i<=sum;i++)
		if(dp[i])
			break;
	printf("%d\n",i);
	return 0;
}

/*


3
1 2 1

2


1

58


*/


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

int main()
{
    int n,m,x;
    cin>>n>>m>>x;
    int toll_count[4]={0};
    int toll;
    for(int i=0 ; i<m ; ++i)
    {
        cin>>toll; 
        ++toll_count[toll<x];
    }
    cout<<min(toll_count[0],toll_count[1])<<endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  
  int a[n+1];
  for(int i=1 ; i<=n ; i++){
    cin >> a[i];
  }
  
  //int check[0];
  //int check[3];
  vector<int> check(n+1,0);
  int x=1;
  int loop=0,count=0;
  
  while(loop==0){
    //cout << "x:" << x << endl;
    //check.push_back(x);
    if(check[x]==0){
      check[x]=x;
    }else{
      loop=1;
      break;
    }
    x=a[x];
    count++;
    if(x==2){
      break;
    }
    
    /*
    for(int i=0 ; i < check.size() ; i++){
      if(x==check[i]){
        loop=1;
      }
    }
    */
  }
  if(loop==1){
    cout << "-1" << endl;
  }else{
    cout << count << endl;
  }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int s(i64 n) {
	std::string w = std::to_string(n);
	
	int ret = 0;
	for(int i = 0; i < w.size(); i++) ret += w[i] - '0';
	return ret;
}

int main(){
	int k; cin >> k;
	const i64 MAX = 1e15;
	std::vector<i64> vec;
	for(i64 i = 0, tmp = 1; i < 15; i++, tmp *= 10) {
		for(int j = 1; j < 1000; j++) vec.push_back(tmp * j + tmp - 1);
	}
	sort(begin(vec), end(vec));
	vec.erase(unique(begin(vec), end(vec)), end(vec));
	
	for(int i = 0; k and i < vec.size(); i++) {
		bool f = true;
		for(int j = i + 1; j < vec.size(); j++) {
			i64 n = vec[i], m = vec[j];
			f &= (__int128_t)n * s(m) <= (__int128_t)m * s(n);
			if(!f) break;
		}
		
		if(f) {
			cout << vec[i] << endl;
			k--;
		}
	}
	return 0;
}


Measured memory_bytes: 512
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * (N)
dp[0] = 0

for i in range(1, N):
    min_from = max(0, i - K)

    temp = float('inf')
    for j in range(min_from, i):
        temp = min(temp, dp[j] + abs(H[i] - H[j]))
    dp[i] =temp

print(dp[N-1])



Measured memory_bytes: 84976
# -*- coding: utf-8 -*-
import numpy as np
A, B, M = map(int, input().split())
a_costs = list(map(int, input().split()))
b_costs = list(map(int, input().split()))
m_discounts = []
for m in range(M):
    tmp = list(map(int, input().split()))
    # m_discounts[[tmp[0], tmp[1]]] = tmp[2]
    m_discounts.append(tmp)
ans = min(a_costs) + min(b_costs)
# no_doscount_min = min(a_costs) + min(b_costs) - discount

for m in m_discounts:
    tmp_ans = a_costs[m[0]-1] + b_costs[m[1]-1] - m[2]
    if (ans > tmp_ans):
        ans = tmp_ans
print(ans)




Measured memory_bytes: 47516
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//#define int long long


int main() {
  string a;
  cin >> a;
 
  a[3]='8';
  
  cout << a << endl;

  
}


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

int main(){
  int y, m, d;
  while(cin>>y>>m>>d){
    if(y<1868 || (y==1868&&m< 9) || (y==1868&&m== 9&&d< 8)){printf("pre-meiji\n"); continue;}
    if(y<1912 || (y==1912&&m< 7) || (y==1912&&m== 7&&d<30)){printf("meiji %d %d %d\n", y-1867, m, d); continue;}
    if(y<1926 || (y==1926&&m<12) || (y==1926&&m==12&&d<25)){printf("taisho %d %d %d\n", y-1911, m, d); continue;}
    if(y<1989 || (y==1989&&m==1&&d<8)){printf("showa %d %d %d\n", y-1925, m, d); continue;}
    printf("heisei %d %d %d\n", y-1988, m, d);
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

ll myabs(ll a)
{
	return a>0 ? a : -a;
}

ll calc(ll a, ll b, ll c)
{
	return max(a, max(b, c)) - min(a, min(b, c));
}

int main()
{
	
	ll a, b;
	cin >> a >> b;
	ll ans = a*b;
	for (ll i = 1; i < a; ++ i)
	{
		ll s1 = i*b;
		ll s2 = b/2*(a-i);
		ll s3 = (b-b/2)*(a-i);
		ans = min(ans, calc(s1, s2, s3));
		s2 = (a-i)/2*b;
		s3 = ((a-i)-(a-i)/2)*b;
		ans = min(ans, calc(s1, s2, s3));
	}
	swap(a, b);
	for (ll i = 1; i < a; ++ i)
	{
		ll s1 = i*b;
		ll s2 = b/2*(a-i);
		ll s3 = (b-b/2)*(a-i);
		ans = min(ans, calc(s1, s2, s3));
		s2 = (a-i)/2*b;
		s3 = ((a-i)-(a-i)/2)*b;
		ans = min(ans, calc(s1, s2, s3));
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
priority_queue<pair<int,int> >q;
int a[200001];
int b[200001];
signed main()
{
	int n,mx=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),mx=max(mx,a[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		if(b[i]>a[i])
			q.push(make_pair(b[i],i));
		else if(b[i]<a[i])
		{
			printf("-1");
			return 0;
		}
	}
	long long ans=0;
	while(!q.empty())
	{
		int at=q.top().second;
		q.pop();
		int tot=((at==1)?b[n]:b[at-1])+((at==n)?b[1]:b[at+1]);
		int time=(b[at]-a[at])/tot;
		if(time==0)
		{
			printf("-1");
			return 0;
		}
		ans+=time;
		b[at]-=time*tot;
		if(b[at]!=a[at])
			q.push(make_pair(b[at],at));
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 3700
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<unordered_map>
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>*/
//#include<ext/rope>
#define ll long long
#define ull unsigned long long
#define INFI 2147483647
#define INFL 9223372036854775807
#define INFU 18446744073709551615
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
const double PI=acos(-1.0);
const double eps=1e-6;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
signed main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    ll x=read(),k=read(),d=read();
    if(x<0LL) x=-x;
    if(x>0LL){
        if(k<=x/d){
            //cout<<"nmsl"<<endl;
            cout<<x-k*d<<endl;
        }
        else{
            ll t=x/d;
            ll shen=k-t;
            if(shen%2==0){
                //cout<<"nmsl"<<endl;
                cout<<x%d<<endl;
            }
            else{
                //cout<<"nmsl"<<endl;
                cout<<d-x%d<<endl;
            }
        }
    }
    else{
        if(k%2LL==0) cout<<0<<endl;
        else cout<<d<<endl;
    }
    return 0;
}


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

int dp[1001];
int w[1001],d[1001];

int main(void){
	int W;
	int N;
	int k=1;
	while(1){
		scanf("%d",&W);
		if(W==0)break;
		memset(dp,0,sizeof(dp));
		memset(w,0,sizeof(w));
		memset(d,0,sizeof(d));
		scanf("%d",&N);
		for(int i=0;i<N;i++){
			scanf("%d,%d",&d[i],&w[i]);
		}
		for(int i=0;i<N;i++){
			for(int j=W;j>=0;j--){
				if(j>=w[i]){
					dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
				}
			}
		}
		int aw=0,ad=0;
		for(int j=0;j<=W;j++){
			if(ad<dp[j]){
				aw=j;
				ad=dp[j];
			}
		}
		printf("Case %d:\n",k);
		printf("%d\n",ad);
		printf("%d\n",aw);
		k++;
	}
    return 0;
}

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

int main() {
  int x,y;
  cin>>x>>y;
  
  bool a=false;
  for(int i=0;i<x+1;i++){
    if(4*x-y-2*i==0){
      a=true;
      break;
    }
  }
  if(a)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


Measured memory_bytes: 3640
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll mod =1e9+7;
const int N = 1e6+7;

 
int main()
{
       int d,n;
       scf(d),scf(n);

       if(n==100)
       n++;

        if(!d)     
        prin(n);

        else if(d==1)
        prin(100*n);

        else
        prin(10000*n);

}  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,T;
  cin >> N;
  T=0;
  vector<long long> v(N,0),c(N,0);
  for (int i=0;i<N;i++) {cin >> v[i];}
  for (int i=0;i<N;i++) {cin >> c[i];}
  for (int i=0;i<N;i++) {
	if (v[i]-c[i]>0) {T+=v[i]-c[i];}
  }
  cout << T << endl;
}


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

int main() {
	int n, l, t[210], ans = 0;
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		t[i] = l + i;
	}
	int hoge, piyo, num = 0;
	for (int i = 0; i < n; i++) {
		if (i == 0) hoge = abs(t[0]);
		else {
			if (hoge > abs(t[i])) {
				hoge = abs(t[i]);
				num = i;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == num)continue;
		ans += t[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << min(a,b) + min(c,d) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>#
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const int mod = 1e9;
using namespace std;

int main() {
	int n;
	cin >> n;
	int a = 0, b = 0, ba = 0,count=0;
	vector<string>s(n);
	repp(i, 0, n)cin >> s[i];
	repp(i, 0, n) {
		repp(j, 0, s[i].size() - 1) {
			if (s[i][j] == 'A' && s[i][j + 1] == 'B')++count;
		}
		if (s[i][0] == 'B' && s[i][s[i].size() - 1] == 'A')++ba;
		else {
			if (s[i][0] == 'B')++b;
			if (s[i][s[i].size() - 1] == 'A')++a;
		}
	}
	if (ba > 0) {
		if (a == 0 && b == 0)--ba;
	}
	cout << count + min(a, b) + ba << endl;
	return 0;
}

Measured memory_bytes: 768
from itertools import product

inf = 10 ** 19

def main():
    n, k = map(int, input().split())
    num_list = list(map(int, input().split()))

    ans = inf

    for bit in list(product([0, 1], repeat = n)):
        count = bit.count(1)
        if count < k:
            continue
        tmp = 0
        max_hight = 0
        for i in range(n):
            if bit[i] != 1:
                max_hight = max(max_hight, num_list[i])
                continue
            if max_hight >= num_list[i]:
                tmp += max_hight - num_list[i] + 1
                max_hight += 1
            else:
                max_hight = num_list[i]
        ans = min(ans, tmp)
    
    print(ans)

if __name__ == '__main__':
    main()

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

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

    int button = 1, count = 0;
    for(int i=0;i<n;i++){
        button = a[button-1];
        count ++;
        if(button == 2){
            cout<<count<<endl;
            break;
        }
    }
    if(count == n) cout<<-1<<endl;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <stack>
#include <array>
#include <fstream>
#include <deque>
#include <bitset>
#include <complex>
using namespace std;
#define REP(i,n) for(int (i) = 0;(i) < (n) ; ++(i))
#define REPS(a,i,n) for(int (i) = (a) ; (i) < (n) ; ++(i))
#define REVERSE(i,n) for(int (i) = n-1;(i) >= 0 ; --i)
#define ALL(c) (c).begin() , (c).end()
#define EACH(it,c) for(auto(it,(c).begin());it != (c).end();)
#define cx real()
#define cy imag()
#define px first
#define py second
#define LL long long
#define int LL
#define inf  (1LL << 60)
#define mod 1000000007
#define QUICK_CIN ios::sync_with_stdio(false); cin.tie(0);
#define lower lower_bound
#define upper upper_bound
#define ZERO(c,n) memset(&c[0],0,sizeof(int)*n)
#define ZERO2(c,n) memset(&c[0][0],0,sizeof(int)*n
#define pl(a) cout << ""#a": " << a << endl;
#ifdef _DEBUG
#define debug_io fstream cin("input.txt");ofstream cout("output.txt");
#else
#define debug_io ;
#endif
#define debug_input debug_io
#define pb(a) push_back(a)
template<class T>void scan(vector<T>& a, int n, istream& cin)
{
	T c; REP(i, n) { cin >> c; a.push_back(c); }
}
using vs = vector<string>; using vi = vector<int>; using pii = pair<int, int>;
using psi = pair<string, int>; using vvi = vector<vi>; using pss = pair<string, string>;
template<class T>bool valid(T x, T w) { return 0 <= x&&x < w; }
int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1, -1 };
//-----------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------


signed main()
{
	QUICK_CIN;
	//debug_input;

	int N;
	cin >> N;

	int ret = 1;

	REP(i, N) {
		ret *= i + 1;
		ret %= mod;
	}

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using Graph = vector<vector<int>>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string N;
  cin >> N;
  if (N.at(1) == '7' || N.at(0) == '7' || N.at(2) == '7')
    cout << "Yes";
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3644
def solve(n, m, a, b):
    if n == 0:
        return 0
    res = 0
    if a >= m:
        res += (n-1) * n // 2 * (a // m)
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    p = (a*n + b) // m
    q = p*m - b
    return res + solve(p, a, m, a*n-q)

t = int(input())
for i in range(t):
    n, m, a, b = map(int, input().split())
    print(solve(n, m, a, b))

Measured memory_bytes: 9148
from operator import itemgetter
import sys


def add(arr, i, size):
    while i < size:
        arr[i] += 1
        i += i & -i


def sub(arr, i, size):
    while i < size:
        arr[i] -= 1
        i += i & -i


def bit_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            sub(bit, li, n + 1)
        last[ci] = i + 1
        add(bit, i + 1, n + 1)
        while i + 1 == r:
            ans[k] = bit_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                print(*ans, sep="\n")
                return


if __name__ == '__main__':
    main()


Measured memory_bytes: 224468
from itertools import combinations_with_replacement

n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(q)]

A=list(combinations_with_replacement(range(1,m+1),n))

res=0

for i in range(len(A)):
    tmp=0
    for j in range(len(l)):
        if A[i][l[j][1]-1]-A[i][l[j][0]-1]==l[j][2]:
            tmp+=l[j][3]

    res=max(res, tmp)

print(res)

Measured memory_bytes: 21632
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }
    let ans = std::cmp::min(a, b) + std::cmp::min(c, d);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,K;
	int a[101];
	int Grundy[100001]={};
	scan(N);scan(K);
	rep(i,N){
		scan(a[i]);
	}
	rep1(i,K){
		bool shutugen[101]={};
		rep(j,N){
			if(i>=a[j]){
				shutugen[Grundy[i-a[j]]]=1;
			}
		}
		rep(j,N+1){
			if(shutugen[j]==0){
				Grundy[i]=j;
				break;
			}
		}
	}
	if(Grundy[K]) prin("First");
	else prin("Second");
	return 0;
}


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

using namespace std;

#define ll long long 
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE 100005


int main()
{
	int n,a,b,coun;
	int arr[10];
	double ashol = 0;
	vector<pair<int,int>>v[10];
	
	cin >> n;
	for(int i = 0; i < n; i++) arr[i] = i+1;
	for(int i  =1; i <= n; i++)
	{
		cin >> a >> b;
		v[i].push_back({a,b});
	}
	do
	{
		for(int i = 0; i < n-1; i++)
		{
			double ans1 = v[arr[i]][0].first;
			double ans2 = v[arr[i]][0].second;
			double ans3 = v[arr[i+1]][0].first;
			double ans4 = v[arr[i+1]][0].second;
			//cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << " ";
			ashol += sqrt(((ans1-ans3)*(ans1-ans3)) + ((ans2-ans4)*(ans2-ans4)));
			//cout << ashol << endl;
		}
		coun++;
		//cout << endl;
	}
	
	while(next_permutation(arr,arr+n));
	cout <<fixed << setprecision(10)<< ashol/(coun*1.0) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 102;

double p[MAX_N];
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> vs; //??°?????????????????????
bool used[MAX_N]; //?????§????????????????????????
int cmp[MAX_N];	//?±????????????£????????????????????????????????????(0????????????)
vector<int> cmp_rev[MAX_N]; //???????????????????????????????????????
bool flag[MAX_N];

void add_edge(int from,int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v)
{
	used[v] = true;
	rep(i,G[v].size()){
		if(!used[G[v][i]]){
			dfs(G[v][i]);
		}
	}
	vs.push_back(v);
}

void rdfs(int v,int k)
{
	used[v] = true;
	cmp[v] = k;
    cmp_rev[k].push_back(v);
	rep(i,rG[v].size()){
		if(!used[rG[v][i]]){
			rdfs(rG[v][i],k);
		}
	}
}

int scc(int n)	//?????£??????????????°?????????
{
	memset(used,0,sizeof(used));
	vs.clear();
	rep(v,n){
		if(!used[v]){
			dfs(v);
		}
	}
	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]]){
			rdfs(vs[i],k++);
		}
	}
	return k;
}

int main()
{
    while(1){
        int n,m;
    	scanf("%d",&n);
        if(n == 0){
            break;
        }
        rep(i,n){
            G[i].clear();
            rG[i].clear();
            cmp_rev[i].clear();
        }
        fill(flag,flag+n,false);
    	rep(i,n){
    		scanf("%lf%d",&p[i],&m);
            rep(j,m){
                int a;
                scanf("%d",&a);
                add_edge(i,a-1);
            }
    	}
        int cnt = scc(n);
        rep(i,n){
            rep(j,G[i].size()){
                if(cmp[i] != cmp[G[i][j]]){
                    flag[cmp[G[i][j]]] = true;
                }
            }
        }
        double res = 1.0;
        rep(i,cnt){
            if(!flag[i]){
                double t = 1.0;
                rep(j,cmp_rev[i].size()){
                     t *= p[cmp_rev[i][j]];
                }
                res *= 1.0 - t;
            }
        }
        printf("%.10f\n",res);
    }
	return 0;
}

Measured memory_bytes: 3360
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);
	return x * y / tmp;
}


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);


	int n, k, x, y;
	cin >> n >> k >> x >> y;


	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (i <= k) {
			ans += x;
		}
		else
		{
			ans += y;
		}
	}

	cout << ans << endl;





	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int n, k;
    string s;

    cin >> n >> k;
    cin >> s;

    int res = 0;
    int l = 0;
    int r = 0;

    //k;
    int a = 0;
    while (true)
    {
        int ol = l;
        int orr = r;

        while (s[r] == '1' && r < s.size())
            r++;

        res = max(res, r - l);

        if (a < k)
        {
            a++;
            while (s[r] == '0' && r < s.size())
                r++;
            while (s[r] == '1' && r < s.size())
                r++;
        }
        else
        {
            a--;
            while (s[l] == '1' && l < s.size())
                l++;
            while (s[l] == '0' && l < s.size())
                l++;
        }

        res = max(res, r - l);

        if (ol == l && orr == r)
            break;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 512
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] a = new int[n+2];
        a[0] = 0;
        a[n+1] = 0;
        long sum = 0;
        for(int i=1; i<=n; i++) {
            a[i] = Integer.parseInt(sc.next());
            sum += sa(a[i-1],a[i]);
        }
        sum += sa(a[n+1],a[n]);
        for(int i=1; i<=n; i++) {
            System.out.println(sum-sa(a[i],a[i-1])-sa(a[i+1],a[i])+sa(a[i+1],a[i-1]));
        }
        
    }
    
    static int sa(int a, int c) {
        if(a <= c) {
            return c-a;
        }else {
            return a-c;
        }
    }
}

Measured memory_bytes: 53696
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define MP(a,b) make_pair(a,b)
typedef long long LL;
typedef pair<int, int> PI;
typedef vector<int> VI;
const LL MOD = 1000000007LL;
LL a[50];
int main() {
	int N;
	cin >> N;
	LL sum = 0;
	rep(i, N) {
		cin >> a[i];
		sum += a[i];
	}
	LL X = sum - (N - 1)*N;
	LL ans = 0;
	if (X > 0) {
		LL l = -1, r = 1LL << 60; //(l,r]
		while (r - l > 1) {
			LL m = (l + r) / 2;
			LL cnt = 0;
			rep(i, N) cnt += max((a[i]+X - m) / (N + 1), 0LL);
			if (cnt <= X) {
				r = m;
			}
			else {
				l = m;
			}
		}
		rep(i, N) {
			ans += max((a[i]+X - r) / (N + 1), 0LL);
			a[i] -= max((a[i]+X - r) / (N + 1), 0LL)*(N + 1);
		}
		rep(i, N) {
			a[i] += ans;
		}
	}
	while (1) {
		LL max_pos = 0;
		rep(i, N) {
			if (a[i] > a[max_pos]) max_pos = i;
		}
		if (a[max_pos] <= N - 1) break;
		a[max_pos] -= N;
		rep(i, N) {
			if (i != max_pos) a[i]++;
		}
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;
int main(){
  int a,b; cin >> a >> b;
  cout << 6-a-b << endl;
}


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

int main(){
    int n, h;
    cin >> h >> n;
    vector<int> a(n), b(n), dp(h+1,1e9);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < h + 1; j++) {
            dp[min(j + a[i], h)] = min(dp[min(j + a[i], h)], dp[j] + b[i]);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

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

int main() {

	int n;
	cin >> n;
	vector<pair<int, int>> ab(n);

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		ab[i] = make_pair(b, a);
	}

	bool flg = false;

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

	int now = 0;

	for (int i = 0; i < n; i++) {
		now += ab[i].second;
		if (now <= ab[i].first) {
			flg = true;
		} else {
			flg = false;
			break;
		}
	}

	if (flg) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 1792
import java.util.Scanner;
import java.util.Arrays;
class Main{
	public static void main(String[] args){
	Scanner in = new Scanner(System.in);
		while(true){
			
			int num[] = new int[2];
			num[0] = in.nextInt();
			num[1] = in.nextInt();
			Arrays.sort(num);
			if(num[0] == 0 && num[1] == 0){
				break;
			}
			System.out.println(num[0] + " " + num[1]);
		}
	}
}


Measured memory_bytes: 35840
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    minus = len([a for a in A if a < 0])
    zero = len([a for a in A if a == 0])
    absA = [abs(a) for a in A]
    low = sorted(absA)[0]
    if minus % 2 == 0:
        return sum(absA)
    elif zero >= 1:
        return sum(absA)
    return sum(absA) - low * 2

print(solve())


Measured memory_bytes: 66916