akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	int N;
	string S, T, ST;
	cin >> N;
	cin >> S >> T;
	for (int i = 0; i < N; i++) {
		ST.push_back(S[i]);
		ST.push_back(T[i]);
	}
	cout << ST << endl;
}

Measured memory_bytes: 256
/*
 * Author       : YangDavid
 * Created Time : 2019年12月28日 星期六 20时34分45秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 203010;
int n, m, v, p, a[maxn];
ll b[maxn];

bool check(int x) {
	if(x > n-p) return true;
	rep(i, n) b[i] = a[i];
	b[x] += m;
	if(b[x] < b[n-p+1]) return false;
	if(v <= p) return true;
	int w = v - p;
	ll cnt = 0;
	for(int i = 1; i <= n-p+1; ++i) if(i != x && b[i] < b[x]) {
		cnt += min(b[x]-b[i], (ll)m);
	}
	return cnt >= 1LL * w * m;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &v, &p);
	rep(i, n) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int l = 1, r = n;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", n - l + 1);

    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define ULL unsigned long int
#define LD long double

LL MOD = 1000000007;

int main(){
    LL n;
    cin >> n;
    string s;
    while(n > 0){
        n = n - 1;
        s += char('a' + n % 26);
        n /= 26;
    }

    reverse(s.begin(), s.end());

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 3612
#include<iostream>
#include<cmath>
#include<bitset>
using namespace std;

int main()
{
    int n, k, b;

    cin >> n;
    cin >> k;

    int u[n];
    double p = pow( 2, (double)n );

    for( int i = 0; i < n; i++ )
        u[i] = i;

    for( int i = 0; i < (int)p; i++ )
    {
        bitset<28> t(i);

        bool judge = true;                  //kの数字分だけ1が立っていれば、それが組み合わせとなる。
        if( t.count() != k )                //count()は1が立っている数を出力する
            judge = false;

        if( judge == true )
        {
            cout << i << ":";
            for( int j = 0; j < 28; j++ )
            {
                if( t[j] == 1 )
                    cout << " " << u[j];
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3300
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	ll a, b, c, d;
	ll cnt, ccnt, dcnt, cdcnt;
	cin >> a >> b >> c >> d;
	cnt = b - a + 1LL;
	ccnt = (b / c) - ((a-1LL) / c);
	dcnt = (b / d) - ((a-1LL) / d);
	cdcnt = (b / ((c*d)/gcd(c,d))) - ((a-1LL) / ((c*d)/gcd(c,d)));
	cout << cnt + cdcnt - (ccnt + dcnt) << endl;
	return 0;
}


Measured memory_bytes: 3628
import sys

n = int(input())
a = [num for num in map(int, input().split())]

if min(a) == 0:
  print(0)
  sys.exit(0)

ans = 1
m = 10 ** 18

for i in range(n):
  ans = ans * a[i]
  
  if ans > m:
    ans = -1
    break

print(ans)

Measured memory_bytes: 84804
lst=[0]*6
for i in range(6):
  lst[i]=int(input())  
N=lst.pop(0)
m=min(lst)
if m<N:
  v1=N//m
  if N%m==0:
    print(5+v1-1)
  else:
    print(5+v1)
else:
  print(5)

Measured memory_bytes: 3060
#include    <iostream>

using namespace std;

int main() {
    unsigned int pairComb[2001] = {0};
    unsigned long long abcdComb[4001] = {0};

    /* 
     * a+b+c+d=Nとなる(a,b,c,d)の組合せは，N=i+jとなる整数i,jに分割し，
     * i,jそれぞれに対し，a+b=i，c+d=jとなる(a,b)と(c,d)を同時に選ぶのと等しい．
     * すなわち，i,jを決定するのは乗法原理がなりたつ．
     * また，i+jに分割する場合は同時に選べないため，加法原理がなりたつ．
     */
    for(int i = 0; i <= 1000; i++)
        for(int j = 0; j <= 1000; j++)
            pairComb[i+j]++;
    
    for(int i = 0; i <= 2000; i++) {
        for(int j = 0; j <= i; j++) {
            abcdComb[i] += pairComb[j] * pairComb[i-j];
        }
    }
    for(int i = 2001; i <= 4000; i++) {
        for(int j = i - 2000; j <= 2000; j++) {
            abcdComb[i] += pairComb[j] * pairComb[i-j];
        }
    }

    int order;
    while(cin >> order) {
        cout << abcdComb[order] << endl;
    }

    return 0;
}


Measured memory_bytes: 3128
#include<iostream>
#include<vector>
#include<string>
#include <cmath>
#include<algorithm>
using namespace std;

int main()
{
	int n,l,i;
	int zero_f = 0;
	int sum = 0;
	cin >> n >> l;
	int aji[1000];
	for( i = 1; i <= n; i++ )
	{
		aji[i] = l + i - 1;
		if( aji[i] == 0 )
		{
			zero_f = 1;
		}
		sum = sum + aji[i];
	}

  sort(aji+1, aji+n);
	if( zero_f == 0 && aji[1] > 0){
	cout << sum - abs( aji[1] ) << endl;
}else if(zero_f == 1)
{
	cout << sum << endl;
}else if( zero_f == 0 && aji[1] < 0 ){
	cout << sum + abs( aji[n] ) << endl;
}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	long long n, k;
	cin >> n >> k;
	long long ans = 0;
	for (long long b = k+1; b <= n; b++) {
		long long tmp0 = (n-k)/b;
		long long tmp1 = tmp0 * b;
		long long y = n - tmp1;
		if (k <= y && y < b) {
			if (y-k+1 >= 1)
				ans += (tmp0) * (y-k+1);
			if (b-1-(y+1)+1 >= 1)
				ans += (tmp0-1) * (b-1-(y+1)+1);
			ans += (b-k);
		} else {
			ans += tmp0*(b-1 -k+1);
			ans += (b-k);
		}
	}
	if (k == 0)
		cout << ans - (n-k) << endl;
	else
		cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3604
import math


def main():
    n = int(input())
    # a, b, t = map(int, input().split())
    # h = list(map(int, input().split()))
    # s = input()
    # h = [int(input()) for _ in rane(n)]

    a = list(map(int, input().split()))
    abs_a = []
    minus = 0
    for ai in a:
        if ai < 0:
            minus += 1
        abs_a.append(abs(ai))

    if minus % 2 == 0:
        print(sum(abs_a))
    else:
        mini = min(abs_a)
        print(sum(abs_a) - 2*mini)


if __name__ == '__main__':
    main()


Measured memory_bytes: 90732
def slove():
    import sys
    input = sys.stdin.readline
    a = int(input().rstrip('\n'))
    b = int(input().rstrip('\n'))
    if a > b:
        print("GREATER")
    elif a < b:
        print("LESS")
    else:
        print("EQUAL")


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38256
#include "iostream"
using namespace std;

int main()
{
    int n, m;
    int sum =0;
    cin>>n>>m;
    int a[m];
    for (int i=0; i<m; ++i){
        cin>>a[i];
        sum = sum + a[i];
    }
    int p= n - sum;
    if (p>= 0){
        cout << p;
    }
    else{
        cout<<"-1";
    }
}

Measured memory_bytes: 3608
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		sc.close();
		int c=a+b;

		if(c%2==0) {
			System.out.println(c/2);
		}
		else {
			System.out.println("IMPOSSIBLE");
		}
	}
}



Measured memory_bytes: 21716
#include <iostream>
using namespace std;
int main(){
  string s;
  while( true ){
    getline(cin,s);
    if( s=="END OF INPUT" )
      break;
    for( int i=0,n=0,len=s.length()+1;i<len;i++ ){
      if( i==len-1 || s[i]==' '){
	cout << n ;
	n=0;
      }else
	n++;
    }
    cout << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; 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 ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

int main() {
    int r; cin >> r;
    cout << 3 * r * r << endl;
    return 0;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp_ITP1_6_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = Int32.Parse(Console.ReadLine());
            string[] input = new string[n];
            input = Console.ReadLine().Split(' ');

            Array.Reverse(input);

            Console.WriteLine(String.Join(" ", input));
        }

    }
}


Measured memory_bytes: 8924
red, green, blue = map(int, input().split())
k = int(input())
success = 0
for cnt in range(k+1):
    if red >= green:
        green *= 2
    elif red >= blue:
        blue *= 2
    elif green >= blue:
        blue *= 2
    else:
        success = 1
        break
if success == 1:
    print('Yes')
else:
    print('No')

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

using namespace std;

pair<int, int> solve(int n) {
    string a = to_string(n);
    return make_pair(a.front()-48, a.back()-48);
}

int main() {

    int n;
    cin >> n;
    int ans = 0;
    int A[10][10] = { 0 };
    for (int i = 1; i < n + 1; i++)
    {
        auto p = solve(i);
        A[p.first][p.second]++;
    }
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            ans += A[i][j] * A[j][i];
        }
    }
    cout << ans << endl;
    return 0;
}

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

int k;
string s;

char next_char(char c){
    if (c == 'z')
    {
        return 'a';
    }

    int i = (int)c + 1;
    return (char)i;
}

int distance_from_a(char c){
    if (c == 'a')
    {
        return 0;
    } else {
        return 26 + (int)'a' - (int)c;
    }
}


int main() {
    cin >> s >> k;
    int n = s.size();

    for (int i = 0; i < n-1; ++i)
    {
        if (k >= distance_from_a(s.at(i)))
        {     
            k = k - distance_from_a(s.at(i));
            s.at(i) = 'a';
        }
    }

    k = k%26;
    while(k>0) {
        s.at(n-1) = next_char(s.at(n-1));
        k--;
    }

    cout << s << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <sstream>
#include <string>


#define rep(i,n) for(int i = 0;i < n;i++)
#define Rep(i,m,M) for(int i = m;i < M;i++)
#define print(var) cout<<#var" = "<<var<<endl;

typedef long long ll;

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;

int N;
ll ans = 0;
vchar str;

bool solve(int n)
{
	ostringstream sout;
	sout << std::setfill('0') << std::setw(3) << n;
	string s = sout.str();
//	print(s[0])
	int i = 0;
		for (int j = 0; j < N and i < 3; j++)
		{
			if (str[j] == s[i])
			{
		//		print(i)
			//		print(j)
				i++;
			}
		}
		return (i == 3);
}

int main()
{
	
	cin >> N;
	str.resize(N);
	rep(i, N)
	{
		cin >> str[i];
	}
/*	int idx = 0,idx2 = 1;
	vector<pair<int, int>> mem;
	while (idx < N and idx2 < N)
	{
		print(idx)
			print(idx2)
		if (idx2 >= N - 2)
		{
			idx++;
			idx2 = idx + 1;
		}
		pair<int, int> p = { str[idx],str[idx2] };
		auto itr = find(mem.begin(), mem.end(), p);
	//	if (itr == mem.end() and mem.size()>0)
		if(count(mem.begin(),mem.end(),p) > 0)
		{
			idx2++;
			continue;
		}
		mem.push_back(p);
		vchar S = str;
		sort(S.begin()+idx2, S.end());
		S.erase(unique(S.begin()+idx2,S.end()), S.end());
		print(S.size());
		ans += S.size();
		idx2++;
	}
	*/
	for (int i = 0; i < 1000; i++)
	{
		if (solve(i))
		{
//			print(i)
			ans++;
		}
	}
	

	cout << ans;
}


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);
		
		int n = sc.nextInt();
		int []a = new int [n];
		long sum = 0;
		
		for(int i = 0 ; i < n ; i++) {
			a[i] = sc.nextInt();
			a[i] = a[i] - i - 1 ;
		}
		Arrays.sort(a);
		int b = 0;
		
		if(n % 2 == 0) {
			 b = (a[n/2] + a[n/2 - 1])/2;
		}
		if(n % 2 == 1){
			b = a[(n-1)/2];
		}
		long ans = 0;
		for(int i = 0; i < n ; i++) {
			ans += Math.abs(a[i] - b);
		}
		System.out.println(ans);

	}

}


Measured memory_bytes: 86992
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main() {
	uint64_t N;
	cin >> N;
	vector<uint64_t>A;
	vector<uint64_t>count(N);
	for (uint64_t i = 0; i < N; i++) {
		uint64_t a;
		cin >> a;
		A.push_back(a-1);
		count[a-1]++;
	}
	uint64_t real_total=0;
	for (uint64_t i = 0; i < N; i++) {
		real_total += count[i] * (count[i] - 1) / 2;
	}

	for (uint64_t k = 0; k < N; k++) {
		
		cout << real_total-(count[A[k]]-1) << endl;
	}


}

Measured memory_bytes: 5872
#include <bits/stdc++.h>
#define MAXN 200100
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const ll mod = 1e9 + 7;


int main (){
    ios_base::sync_with_stdio(false);
    int a, b;

    cin >> a >> b;

    cout << max(a+b, max(a*b, a-b)) << endl;
    return 0;
}

Measured memory_bytes: 256
///Boot camp for Beginners
///Easy 100
///Problem-11
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int n,k;
    int ans=01;
    cin>>n;

    while(ans*2<=n)
    {
        ans=ans*2;
    }
   cout<<ans<<endl;

    return 0;
}


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

vector <bool> s; /// 1 dif

vector <bool> f(double a, double b);

int main()
{
    int n;
    cin >> n;
    string sr;
    cin >> sr;
    for (auto i : sr)
        s.push_back(i == 'o' ? 0 : 1);

    vector <bool> a(f(1, 1)), b(f(1, 0)), c(f(0, 1)), d(f(0, 0));

    if (!b.empty())
        swap(a, b);
    if (!c.empty())
        swap(a, c);
    if (!d.empty())
        swap(a, d);

    if (a.empty()) {
        cout << -1;
        return 0;
    }

    for (auto i : a)
        cout << (i ? 'W' : 'S');

    return 0;
}


vector <bool> f(double a, double b) /// 1 minte
{
    vector <bool> ans = s;
    ans[0] = a;
    ans[1] = b;
    for (int i(2); i < s.size(); i++) {
        ans[i] = ans[i - 1] ^ ans[i - 2] ^ s[i - 1];
    }
    int n = s.size() - 1;
    if (ans[0] != ans[n] ^ ans[n - 1] ^ s[n] || ans[n] != ans[0] ^ ans[1] ^ s[0])
        ans.clear();
    return ans;
}


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

int main() {
  string A,B,C;
  cin >> A >> B >> C;
  int a=A.size();
  int b=B.size();
  int c=C.size();
  if (A.at(a-1)==B.at(0) && B.at(b-1)==C.at(0)) cout << "YES" << endl;
  else cout << "NO" << endl;
}


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


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
        	String str  = br.readLine();
        	if(str.equals("-"))break;
        	int n = Integer.parseInt(br.readLine());
        	for(int i=0; i< n;i++){
        		int h = Integer.parseInt(br.readLine());
        		str = str.substring(h, str.length()) + str.substring(0,h);
        	}
        	System.out.println(str);
    	}
    }
}

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

int main(){
	long long X;
	cin >> X;
	long long A = 140, B = 140;
	for(long i=-120;i<120;i++){
		for(long j=-120;j<120;j++){
			if(i*i*i*i*i - j*j*j*j*j == X){
				A = i;
				B = j;
				break;
			}
		}
		if(A != 140)break;
	}
	cout << A << " " << B << endl;
}

Measured memory_bytes: 3624
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

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

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

int main()
{
	int n, k;
	cin >> n >> k;

	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a.at(i);
	}

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

	ll ans = inf;
	int r = 0;
	for (int i = 0; i <= n - k; i++)
	{
		ans = min(ans, a.at(i + k - 1) - a.at(i));

	}

	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>

#define MAX 100001

using namespace std;

int main(){
  int n; cin >> n;
  int a[n+1],cnt[MAX];
  for(int i=0;i<MAX;i++) cnt[i]=0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    cnt[a[i]]++;
  }
  int maxsum=0;
  for(int i=0;i<MAX-2;i++){
    int sum=cnt[i]+cnt[i+1]+cnt[i+2];
    maxsum=max(maxsum,sum);
  }
  cout << maxsum << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

int main() {
	ll x, k, d;
	cin >> x >> k >> d;
	ll abx = abs(x);
	ll q, qq;
	if (abx >= d) {
		 q = abx / d;
		 qq = q + 1;
		 if (q >= k) {
			 q = k;
		 }
	}
	else {
		ll xx = abs(abx - d);
		if (k %2 ==1) {
			cout << xx;
		}
		else {
			cout <<abx;
		}
		return 0;
	}
	ll ans;
	if ((k - q) % 2 == 0 || q==k) {
		if (x >= 0)ans = x - q * d;
		if (x < 0)ans = x + q * d;
	}
	else {
		if (x >= 0)ans = x - qq * d;
		if (x < 0)ans = x + qq * d;
	}
	cout << abs(ans);
	return 0;
}

Measured memory_bytes: 3552
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#define LL long long
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 20160116
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}
bool dp[105][10005];
int a[105];
int main(){
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	dp[0][0]=true;
	for (int i=1;i<=n;i++){
		for (int j=0;j<10005;j++){
			dp[i][j]=dp[i-1][j];
			if (j>=a[i-1]) dp[i][j]|=dp[i-1][j-a[i-1]];
		}
	}
	int ans=0;
	for (int i=0;i<10005;i++) if (i%10 && dp[n][i]) ans=max(ans,i);
	printf("%d\n",ans);
}

Measured memory_bytes: 1280
#define _CRT_SECURE_NO_DEPRECATE
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define ll  long long int 
 
int main() {
	//freopen("test.txt", "r", stdin);
	int n,ans=0; cin>>n;
	while(n/500){
		n-=500;
		ans+=1000;
	}
	while(n/5){
		n-=5;
		ans+=5;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
S = input()
T = input()
if len(S)!=len(T):
    print('No')
    sys.exit()
S = S+S
for i in range(len(T)):
    flag = True
    for j in range(len(T)):
        if S[i+j] != T[j]:
            flag = False
    if flag:
        print('Yes')
        sys.exit()
print('No')


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

int main(){
  int n, t, i;
  
  while(1){
    
    int a[30] = {}, max = 28, s  =29, ans = 0;
    char c;
    
    cin>>n;
    if(n == 0) break;

    for(i = 1; i <= n; i++){
      cin>>c;
      
      t = c -'A';

      a[t]++;
      

      
      if(a[t] >= a[max]){
		if(max != t) {
			s = max; 
			max = t;
		}
      }else if (a[t] > a[s]) {
		s = t; 
      }
      
        if(a[max] > a[s] + n - i && ans == 0)
       	ans = i;
      
    }
      c = max + 'A';

      if(a[max] == a[s]) cout<<"TIE"<<endl;
      else cout<<c<<" "<<ans<<endl;
    
  }
	return 0;
}



Measured memory_bytes: 3076
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()
ans = 1
th = 10 ** 18
if 0 in A:
    print(0)
    exit()
for a in A:
    ans *= a
    if ans > th:
        print(-1)
        exit()
print(ans)


Measured memory_bytes: 83320
#include <stdio.h>
int main(void){
    long long int n,k,r,s,p,i,g=0;
    scanf("%lld %lld %lld %lld %lld",&n,&k,&r,&s,&p);
    char t[n+1];
    scanf("%s",t);
    for(i=0;i<n;i++){
        if(i-k<0){
            if(t[i]=='r') g+=p;
            else if(t[i]=='s') g+=r;
            else g+=s;
        }
        else{
            // printf("%c %c\n",t[i-k],t[i]);
            if(t[i-k]!=t[i]){
                if(t[i]=='r') g+=p;
                else if(t[i]=='s') g+=r;
                else g+=s;
            }
            else t[i]='q';
        }
        // printf("%lld回目終了：%lld点\n",i,g);
    }
    printf("%lld",g);
}


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

#define ld long double
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vl vector<ll>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define repd(i, a, b) for (int i=(a);i<(b);i++)
#define rep(i, n) repd(i,0,n)
#define ALL(v) v.begin(), v.end()
#define INF 1e9

using namespace std;

/**
 * calculate GCD(greatest common divisor)
 * @param a
 * @param b
 * @return
 */
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

/**
 * change minimum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMinimum(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * change maximum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMaximum(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * output answer
 * @tparam T
 * @param answer
 * @return
 */
template<typename T>
T output(T answer) {
    cout << answer << endl;
    return 0;
}

/** ----from here ---------------------------------------------------------- */

int main() {

    int N, M;

    cin >> N >> M;
    vector<int> f(N, 1);// とりあえず全て言い展望台に
    vector<int> h(N);// とりあえず全て言い展望台に

    for (int i = 0; i < N; ++i) {
        cin >> h[i];
//        cout << h[i]<<endl;
    }


    int a, b;
    int ha, hb;
    for (int i = 0; i < M; ++i) {
        cin >> a >> b;
        ha = h[a - 1];
        hb = h[b - 1];
//        cout << "ha" << ha << endl;
//        cout << "hb" << hb << endl;
        if (ha >= hb) {
            f[b - 1] = 0;
        }
        if (ha <= hb) {
            f[a - 1] = 0;
        }

    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
//        cout << h.at(i) << endl;
        if (f.at(i) == 1) {
//            cout << i << endl;
            ans++;
        }
    }

    cout << ans << endl;


}

Measured memory_bytes: 4048
#include <iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <algorithm>
#define ll long long
#define pr pair<int,int>
#define all vec.begin(),vec.end()
#define REP(i,a,b) for (int i = a; i < b; i++)
#define fi first
#define se second
#define pushb push_back
#define makep make_pair

using namespace std;

int main(){
	string a,b;
	cin >> a >> b;
	for(int i = 0; i < a.size() + b.size(); i++){
		if(i % 2 == 0)
			cout << a[i /2];
		else
			cout << b[i /2];
	}
	return 0;
}



Measured memory_bytes: 256
#include<bits//stdc++.h>
using namespace std;
#define req(i,n) for(int i = 1;i <=n;i++)
typedef long long ll;
ll sum = 0,ans,n,k,cnt =0,r,c,d,ma,mi; 
int main() {
    cin >> n >> k; sum = (n / 3 + 1) * k - (n / 3) * k;
    sum = min((k / 3 + 1) * n - (k / 3) * n, sum);
    if (n % 3 == 0 || k % 3 == 0) {
        cout << 0 << endl;
        return 0;
    }
    else {
        req(i, n - 1) {
            r = i * k;
            c = (n - i) * (k / 2 + k % 2);
            d = (n - i) * (k / 2);
            ma = max(r, max(c, d));
            mi = min(r, min(c, d));
            sum = min(sum, ma - mi);
        }
        req(i, k - 1) {
            r = i * n;
            c = (k - i) * (n / 2 + n% 2);
            d = (k - i) * (n / 2);
            ma = max(r, max(c, d));
            mi = min(r, min(c, d));
            sum = min(sum, ma - mi);
        }
    }
    cout << sum << endl;
}

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

int v[110], w[110];
const int64_t LINF = 1001001001001001001;
int64_t dp[110][111000];

int main() {
    int n, W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (int j = 1; j < 110000; j++) {
        dp[0][j] = LINF;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 110000; j++) {
            dp[i][j] = dp[i-1][j];
            if (j-v[i] >= 0) {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }

    int ans = 0;
    for (int v = 0; v < 110000; v++) {
        if (dp[n][v] <= W) {
            ans = max(ans, v);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 88320
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		double n = sc.nextDouble();
		sc.close();

		double x = n / 1.08;
		int a = (int) Math.ceil(x);

		int n1 = (int) Math.floor((a - 1) * 1.08);
		int n2 = (int) Math.floor(a * 1.08);
		int n3 = (int) Math.floor((a + 1) * 1.08);

		if (n == n1 || n == n2 || n == n3) {
			System.out.println(a);
		} else {
			System.out.println(":(");
		}

	}

}


Measured memory_bytes: 25172
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n;
ll a[410],dp[410][410];
int main() {
	scanf("%d",&n);
	int i,j,k,l;
	for(i=1;i<=n;i++) scanf("%lld",a+i),a[i]+=a[i-1];
	for(l=2;l<=n;l++) {
		for(i=1;i<=n-l+1;i++) {
			j=i+l-1;
			dp[i][j]=9e18;
			for(k=i;k<j;k++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]);
		}
	}
	printf("%lld",dp[1][n]);
	return 0;
}

Measured memory_bytes: 1664
num = int(input())
k=0
ans=[]
while k<1:
    if num<=26:
        ans.append((chr(96+num)))
        k=1
    elif num%26==0:
        num=(num//26-1)
        ans.append((chr(96+26)))
    else:
        ans.append((chr(96+num%26)))
        num=(num//26)

for i in range(len(ans)-1,-1,-1):
    if i ==0:
        print(ans[i])
    else:
        print(ans[i], end="")

Measured memory_bytes: 9180
use proconio::input;

fn main() {
  input! {
    x: f64,
  }
  
  let mut m: f64 = 100.;
  let mut y = 1;
  
  loop  {
    m += m * 0.01;
    m = m.floor();
    if m >= x {
      break;
    }
    y += 1;
  }
  
  println!("{}", y);
  
}

Measured memory_bytes: 2692
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 20;
const int LIM = 55;
const int MASK = (1 << 18);
const int INF = 1000000001;

int n;
int a[MAX][2];
int dyn[MASK][LIM];

int recurse(int mask, int last, int idx) {
    if (idx >= n)
        return 0;
    int& ans = dyn[mask][last];
    if (ans != -1)
        return ans;
    
    ans = INF;

    vector <int> parity(n, 0);
    int cur = 0;
    for (int i = n - 1; i >= 0; i--) {
        cur ^= !!(mask & (1 << i));
        parity[i] = cur;
    }

    int dist = 0;
    for (int i = 0; i < n; i++) if (!(mask & (1 << i))) {
        int side = parity[i] ^ (dist % 2);
        if (a[i][side] >= last) {
            ans = min(ans, recurse(mask | (1 << i), a[i][side], idx + 1) + dist);
        }
        dist++;
    }
    
    return ans;
}

int solve() {
    memset(dyn, -1, sizeof(dyn));
    int ans = recurse(0, 0, 0);
    return ans >= INF ? -1 : ans;
}

int main(void) {
	// in = fopen("D.in", "rt");
	
	fscanf(in, "%d", &n);
	for (int i = 0; i < 2; i++) {
	    for (int c = 0; c < n; c++) {
	        fscanf(in, "%d", &a[c][i]);
        }
    }
    fprintf(out, "%d\n", solve());
	
	return 0;
}

Measured memory_bytes: 56576
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> X(N);
    for(int i=0; i<N; i++) {
        cin >> X[i];
    }

    vector<int> s = X;
    sort(s.begin(), s.end());
    for(int i=0; i<N; i++) {
        if(X[i] >= s[N/2]) {
            cout << s[N/2-1] << endl;
        } else {
            cout << s[N/2] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3712
import java.util.*;

public class Main {
  public static void main(String[] args) {
    int N, D;
    int[][] X;
    try(Scanner sc = new Scanner(System.in)) {
      N = sc.nextInt();
      D = sc.nextInt();
      X = new int[N][D];
      for(int i = 0; i < N; i++) {
        X[i] = new int[D];
        for(int d = 0; d < D; d++) {
          X[i][d] = sc.nextInt();
        }
      }
    }
    int count = 0;
    for(int i = 0; i < N; i++) {
      for(int j = i+1; j < N; j++) {
        int rSquared = 0;
        for(int d = 0; d < D; d++) {
          int diff = X[i][d] - X[j][d];
          rSquared += diff * diff;
        }
        double r = Math.sqrt(rSquared);
        if ( isOk(r) ) {
          count++;
        }
      }
    }
    System.out.println(count);
  }
  
  private static boolean isOk(double value) {
    int intValue = (int)Math.floor(value);
    return value == (double)intValue;
  }
}

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

typedef pair<int, char> P;

int getLevel(string &expr) {
    int ret = 0;
    while(expr[ret] == '.') ret++;
    return ret;
}

bool isdigit(char c) {
    return c >= '0' && c <= '9';
}

int process(vector<string> &expr, int* line) {
    int ret;
    int level = getLevel(expr[*line]);
    if(level == 0 && isdigit(expr[*line][level])) 
        return expr[*line][level]-'0';
    else if(expr[*line][level] == '+') {
        (*line)++;
        ret = 0;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret += expr[*line][new_level]-'0';
                else 
                    ret += process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    } else if(expr[*line][level] == '*') {
        (*line)++;
        ret = 1;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret *= expr[*line][new_level]-'0';
                else 
                    ret *= process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    }
}

int main(void){
    int n;
    string s;
    vector<string> expr;
    while(cin >> n && n) {
        cin.ignore();
        expr.clear();
        rep(i, n) {
            getline(cin, s);
            expr.push_back(s);
        }
        int line = 0;
        cout << process(expr, &line) << endl;
    }
}

Measured memory_bytes: 1216
k = %[Man Oku Cho Kei Gai Jo Jou Ko Kan Sei Sai Gok Ggs Asg Nyt Fks Mts].split.to_a
while gets
  m, n = $_.split.map(&:to_i)
  break if m == 0 && n == 0
  v = m ** n
  a = Math.log10(v).to_i / 4
  (1..a).each do |i|
    x = 10 ** (4 * (a-i+1) )
    y = v / x
    print y, k[a-i] if y != 0
    v -= y * x
  end
  print v if v != 0
  puts
end

Measured memory_bytes: 8964
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long[] a = new long[1000001];
        for(int i = 1; i <= 9; i++){
        	a[i] = i;
        }
        int cnt = 10;
        int x = 0;
        for(int i = 1; i <= 9; i++){
    		long d = a[i]%10;
    		if(d == 0){
    			a[cnt++] = a[i]*10;
    			a[cnt++] = a[i]*10+1;
    			x+=2;
    		}
    		else if(d==9){
    			a[cnt++] = a[i]*10+8;
    			a[cnt++] = a[i]*10+9;
    			x+=2;
    		}
    		else{
    			a[cnt++] = a[i]*10+d-1;
    			a[cnt++] = a[i]*10+d;
    			a[cnt++] = a[i]*10+d+1;
    			x+=3;
    		}
    	}
        int l = 10,r = 10+x;
        x = 0;
        for(int i = l; i <= r; i++){
        	long d = a[i]%10;
    		if(d == 0){
    			a[cnt++] = a[i]*10;
    			a[cnt++] = a[i]*10+1;
    			x+=2;
    		}
    		else if(d==9){
    			a[cnt++] = a[i]*10+8;
    			a[cnt++] = a[i]*10+9;
    			x+=2;
    		}
    		else{
    			a[cnt++] = a[i]*10+d-1;
    			a[cnt++] = a[i]*10+d;
    			a[cnt++] = a[i]*10+d+1;
    			x+=3;
    		}
        }
        
        for(int k = 1; k <= 7; k++){
        	l = r+1;
            r = l+x;
            x = 0;
            for(int i = l; i <= r; i++){
            	long d = a[i]%10;
        		if(d == 0){
        			a[cnt++] = a[i]*10;
        			a[cnt++] = a[i]*10+1;
        			x+=2;
        		}
        		else if(d==9){
        			a[cnt++] = a[i]*10+8;
        			a[cnt++] = a[i]*10+9;
        			x+=2;
        		}
        		else{
        			a[cnt++] = a[i]*10+d-1;
        			a[cnt++] = a[i]*10+d;
        			a[cnt++] = a[i]*10+d+1;
        			x+=3;
        		}
            }
        }
        int n = cin.nextInt();
        System.out.println(a[n]);
    }
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    int N;
    cin >> N;
    if (N == 1) {
        cout << "Hello World\n";
    }
    else {
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;
    }

    return 0;
}

Measured memory_bytes: 256
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }


int main() {
	
	ll N, Q;
	cin >> N >> Q;
	string s;
	cin >> s;
	vector<char> t(Q), d(Q);
	rep(i, Q) cin >> t[i] >> d[i];

	ll x = 0, y = N - 1;
	ford(i, 0, Q) {
		if (d[i] == 'L' && s[x] == t[i]) x++;
		if (d[i] == 'R' && x != 0 && s[x - 1] == t[i]) x--;
	}
	ford(i, 0, Q) {
		if (d[i] == 'R' && s[y] == t[i]) y--;
		if (d[i] == 'L' && y + 1 != N && s[y + 1] == t[i]) y++;
	}

	cout << N - x - (N - 1 - y) << endl;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
int A,B,L,R;
void work0(){
	For(i,L,R)
		putchar(i&1?'A':'B');
	puts("");
}
void work1(){
	int v1=max(A,B),v2=min(A,B)+1; 
	int k=v1/v2+(v1%v2!=0);
	int l=1,r=A,ans=0;
	while (l<=r){
		int mid=(l+r)/2;
		int pref=(mid-1)/k;
		if (1ll*(A-mid+1)*k>=B-pref)
			ans=mid,l=mid+1;
		else r=mid-1;
	}
	int len1=ans+max(ans-1,0)/k;
	For(i,L,R)
		if (i<=len1)	
			putchar(i%(k+1)?'A':'B');
		else{
			int ii=A+B-i+1;
			putchar(ii%(k+1)?'B':'A'); 
		}
	puts("");
}
void solve(){
	scanf("%d%d%d%d",&A,&B,&L,&R);
	if (A==B) work0();
	else work1();
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--) solve();
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 

using namespace std;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))

int main()
{
	int a, b, k, count = 0;
	cin >> a >> b >> k;
	for (int i = 100; 0 <= i; --i)
	{
		if (a%i == 0 && b%i == 0)++count;
		if (count == k)
		{
			cout << i << endl;
			return 0;
		}
	}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mk make_pair

template <class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

/*
    if you have any question about any part of my code,
    please don't shy to ask anytime :)
*/



void solve()
{
    ll n,k;
    cin>>n>>k;
    unordered_map<ll,ll>h;
    while(k--)
    {
        ll m;
        cin>>m;
        while(m--)
        {
            ll a;
            cin>>a;
            h[a]++;
        }
    }

    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(h[i]==0)
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    
}

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

    // ll t;
    // cin >> t;

    // while (t--)
    // {
    //     solve();
    // }
    solve();
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    int N,M,Q;
    cin >> N >> M >> Q;
    string S[N];
    int Ntable[2010][2010] = {},Mtable[2010][2010] = {},Qtable[2010][2010] ={};
    REP(i,N){
        cin >> S[i];
        REP(j,M){
            if(S[i][j] == '1'){
                Qtable[i][j+1] = Qtable[i][j] + 1;
            }
            else Qtable[i][j+1] = Qtable[i][j];
        }
    }
    int X1[Q],Y1[Q],X2[Q],Y2[Q];
    REP(i,N){
        REP(j,M){
            if(j >= 1){
                if(S[i][j-1] == '1' && S[i][j] == '1'){
                    Mtable[i][j] = Mtable[i][j-1] + 1;
                }
                else Mtable[i][j] = Mtable[i][j-1];
            }
            if(i >= 1){
                if(S[i-1][j] == '1' && S[i][j] == '1'){
                    Ntable[i][j] = Ntable[i-1][j] + 1;
                }
                else Ntable[i][j] = Ntable[i-1][j];
            }
        }
    }
    REP(i,Q){
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
        X1[i]--;Y1[i]--;X2[i]--;Y2[i]--;
        int len = 0;
        int sum = 0;
        REPP(j,X1[i],X2[i]+1){
            len += Mtable[j][Y2[i]] - Mtable[j][Y1[i]];
        }
        REPP(j,Y1[i],Y2[i]+1){
            len += Ntable[X2[i]][j] - Ntable[X1[i]][j];
        }
        REPP(j,X1[i],X2[i]+1){
            sum += Qtable[j][Y2[i]+1] - Qtable[j][Y1[i]];
        }
        cout << sum - len << endl;
    }
}

Measured memory_bytes: 57856
/*{{{*/
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1<<20;
char t[SIZE];
LL mi[SIZE],ma[SIZE];
int f(int st,int n){
    if(n&1){
        return (1-(st&1)+n)/2;
    }
    else return n/2;
}
int main(){
    RS(t+1);
    int n=LEN(t+1);
    int one_cnt=count(t+1,t+n+1,'1');
    int zero_cnt=0;
    LL an=0;
    FOR(i,1,one_cnt){
        an+=(i+1)/2;
    }
    for(int i=1,j;i<=n;i=j){
        if(t[i]=='0'){
            zero_cnt++;
            j=i+1;
        } else {
            for(j=i+1;j<=n&&t[j]=='1';j++);
            int num=j-i;
            an+=num/2*(n-one_cnt);
            if(num&1){
                an+=n-one_cnt-f(i,zero_cnt);
            }
        }

    }
    W(an);
    return 0;
}


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

diff_list = []
for i in range(N - 1):
    current = A[i]
    next = A[i + 1]
    diff_list.append(next - current)

diff_list.append(K - A[-1] + A[0])

max_index = diff_list.index(max(diff_list))
del diff_list[max_index]

print(sum(diff_list))


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

"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・自力AC
・トポロジカルソート
・解説読んで、DPする位置をちょっと変えてみた。
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N, dag):
    # ここからトポロジカルソート準備
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(dag)):
        # 流入するノード数
        incnts[dag[i][1]] += 1
        # 流出先ノードのリスト
        outnodes[dag[i][0]].append(dag[i][1])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            if incnts[node] == 0:
                S.add(node)

        # そのノードの順序確定時に答えの更新もやればループは減ると思う
        src = L[-1]
        for dest in nodes[src]:
            dp[dest] = max(dp[dest], dp[src]+1)
    return L

N, M = MAP()
nodes = [[] for i in range(N)]
edges = [None] * M
for i in range(M):
    x, y = MAP()
    nodes[x-1].append(y-1)
    edges[i] = ((x-1, y-1))

dp = [0] * N
# この後の最大値更新で矛盾が生じないようにソートしておく
l = topological_sort(N, edges)

print(max(dp))


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

#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string s; cin >> s;
    int cnt=0,mx=0;
    for(int i=0;i<3;i++){
        if(s[i]=='R'){
            ++cnt;
            if(i==2) mx = max(mx,cnt);
        }
        else{
            mx = max(mx,cnt);
            cnt=0;
        }
    }
    cout << mx << '\n';
    return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
int main(void)
{
	int a[4],b[4],c[4],d;
	for (d=1;d<=4;d++)
	{
		scanf("%d %d",&a[d],&b[d]);
		if (a[d]==1)
		{
			a[d]=6000;
		}
		else if (a[d]==2)
		{
			a[d]=4000;
		}
		else if (a[d]==3)
		{
			a[d]=3000;
		}
		else if (a[d]==4)
		{
			a[d]=2000;
		}
	c[d]=a[d]*b[d];
	printf("%d\n", c[d]);
	}
	return 0;
}

Measured memory_bytes: 2728