akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 210000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
int p[30][30];
long long dp[1<<21];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)for(int j=0;j<a;j++)scanf("%d",&p[i][j]);
	dp[0]=1;
	for(int i=0;i<(1<<a)-1;i++){
		int n=__builtin_popcount(i);
		for(int j=0;j<a;j++){
			if(i&(1<<j))continue;
			if(!p[n][j])continue;
			dp[i+(1<<j)]=(dp[i+(1<<j)]+dp[i])%mod;
		}
	}
	printf("%lld\n",dp[(1<<a)-1]);
}

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

using namespace std;

int main() {
	string S;
	int answer = 0;

	cin >> S;

	for (int i = 0; i < S.size(); ++i) {
		if (S[i] == '+') {
			++answer;
		}
		else if (S[i] == '-') {
			--answer;
		}
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int ans = 0;
	int N;
	cin >> N;
	for(int i=1; i<32; ++i){
		for(int j=2; j<10; ++j){
			if(pow(i, j) <= N){
				ans = max(ans, (int)pow(i, j));
			}else break;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4100
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int Q = sc.nextInt();
		long[] s = new long[A + 2];
		long[] t = new long[B + 2];
		long[] x = new long[Q];
		for(int i = 1; i <= A; i++) {
			s[i] = sc.nextLong();
		}
		for(int i = 1; i <= B; i++) {
			t[i] = sc.nextLong();
		}
		for(int i = 0; i < Q; i++) {
			x[i] = sc.nextLong();
		}
		sc.close();
		long INF = (long)(Math.pow(10, 11));
		s[0] = t[0] = -INF;
		s[A + 1] = t[B + 1] = INF;
		for(int i = 0; i < Q; i++) {
			int a = bs(s, x[i]);
			int b = bs(t, x[i]);
			long m0 = Math.min(s[a - 1], t[b - 1]);
			long m1 = Math.max(s[a], t[b]);
			long l = Long.MAX_VALUE;
			l = Math.min(l, 2 * (x[i] - s[a - 1]) + t[b] - x[i]);
			l = Math.min(l, 2 * (s[a] - x[i]) + x[i] - t[b - 1]);
			l = Math.min(l, 2 * (x[i] - t[b - 1]) + s[a] - x[i]);
			l = Math.min(l, 2 * (t[b] - x[i]) + x[i] - s[a - 1]);
			l = Math.min(l, x[i] - m0);
			l = Math.min(l, m1 - x[i]);
			System.out.println(l);
		}

	}
	static int bs(long[] a, long k) {
		int l = -1;
		int r = a.length;
		while(r - l > 1) {
			int mid = (r + l) / 2;
			if(a[mid] > k) {
				r = mid;
			}else {
				l = mid;
			}
		}
		return r;
	}
}

Measured memory_bytes: 97268
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second

using Graph = vector<vector<int>>;

int main()
{
    string s;
    cin >> s;
    ll n = s.size();
    vector<ll> mod(n);
    mod[n - 1] = 1;
    for (ll i = n - 2; i >= 0; i--)
    {
        mod[i] = (mod[i + 1] * 10) % 2019;
    }
    vector<ll> dp(n);
    dp[n - 1] = (s[n - 1] - '0');
    for (ll i = n - 2; i >= 0; i--)
    {
        dp[i] = (dp[i + 1] + ((s[i] - '0') * mod[i])) % 2019;
    }
    dp.push_back(0);

    map<ll, ll> m;
    for (ll i = 0; i < n + 1; i++)
    {
        if (m.count(dp[i]) == 0)
        {
            m[dp[i]] = 1;
        }
        else
        {
            m[dp[i]] += 1;
        }
    }
    ll ans = 0;
    for (auto itr = m.begin(); itr != m.end(); itr++)
    {
        ans += itr->second * (itr->second - 1) / 2;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 8372
n, m = map(int,input().split())
s_x_plus_y = []
s_x_minus_y = []
p_x_plus_y = []
p_x_minus_y = []

for student in range(n):
    x, y = map(int,input().split())
    s_x_plus_y.append(x + y)
    s_x_minus_y.append(x - y)

for i in range(m):
    x, y = map(int,input().split())
    p_x_plus_y.append(x + y)
    p_x_minus_y.append(x - y)


for i in range(n):
    p_dist = []
    for j in range(m):
        p1 = abs(s_x_plus_y[i] - p_x_plus_y[j])
        p2 = abs(s_x_minus_y[i] - p_x_minus_y[j])
        d = max(p1, p2)
        p_dist.append(d)
    print(p_dist.index(min(p_dist))+1)


Measured memory_bytes: 9140
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

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

using ll = long long;

ll b, c, a;

int main()
{
  std::cin >> b >> c >> a;

  std::cout << (b*c)/2 << std::endl;

  return 0;
}

Measured memory_bytes: 256
import queue

class graph:
    def __init__(self, n):
        self.node = [[] for _ in range(n)]
        self.unexplored = [True for _ in range(n)]
        self.link = []
    
    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def get_node(self):
        return self.node

    def bfs(self, start, idx):
        self.unexplored[start] = False
        self.link[idx].append(start)
        d = queue.deque()
        d.extend(self.node[start])
        while d:
            vis = d.popleft()
            if self.unexplored[vis]:
                self.link[idx].append(vis)
                self.unexplored[vis] = False
                d.extend(self.node[vis])
    
    def split_link(self):
        idx = 0
        for i in range(len(self.node)):
            if self.unexplored[i]:
                self.link.append([])
                self.bfs(i, idx)
                idx += 1

    def get_linklen(self):
        return [len(x) for x in self.link]

n, m = map(int, input().split())
g = graph(n)
for _ in range(m):
    a, b = map(int, input().split())
    g.unit(a-1, b-1)

g.split_link()
print(max(g.get_linklen()))


Measured memory_bytes: 53588
#include <cmath>
#include <iostream>
#include <vector>

int main() {
  int n, d;
  std::cin >> n >> d;

  std::vector<std::vector<int>> points;
  for (int i = 0; i < n; ++i) {
    std::vector<int> point(d);
    for (int j = 0; j < d; ++j) {
      int x;
      std::cin >> point[j];
    }
    points.push_back(point);
  }

  int count = 0;

  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      auto &pi = points[i];
      auto &pj = points[j];

      int sum = 0;
      for (int k = 0; k < d; ++k) {
        auto diff = pi[k] - pj[k];
        sum += diff * diff;
      }

      int rt = std::sqrt(sum);

      if (rt * rt == sum) {
        ++count;
      }
    }
  }

  std::cout << count << std::endl;
  return 0;
}

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

struct VertexDistance {

	int first;
	int second;

	VertexDistance(int f, int s) : first(f), second(s) {}

};

bool operator< (const VertexDistance &a, const VertexDistance &b) {
	return a.second > b.second;
}
		

int v, e, startVertex;
vector<vector<pair<int, int> > > vertex;
priority_queue <VertexDistance> que;
int vertexDistance[100005];
char visitedVertex[100005];

const char Yet = '1';
const char Now = '2';
const char Finish = '3';
const int INF = 1 << 30;

void Init();

int main() {



	cin >> v >> e >> startVertex;

	Init();

	for (int i = 0; i < e; ++i) {

		int s, t, d;
		cin >> s >> t >> d;

		vertex[s].push_back(make_pair(t, d));

	}

	/*
	for (int i = 0; i < v; ++i) {
		cout << i << " : ";
		for (int j = 0; j < vertex[i].size(); ++j) {
			cout << vertex[i][j].first << "->" << vertex[i][j].second << ", ";
		}
		cout << endl;
	}
	*/

	que.push(VertexDistance(startVertex, 0));

// 	cout << endl << endl;

	while (!que.empty()) {

		VertexDistance nowVertex = que.top();
		que.pop();
		int nowV = nowVertex.first;
		int nowD = nowVertex.second;

		if (visitedVertex[nowV] == Finish)
			continue;


		visitedVertex[nowV] = Finish;
		vertexDistance[nowV] = nowD;
//		cout << nowV << " : " << nowD << endl;
		for (int i = 0; i < vertex[nowV].size(); ++i) {

			if (visitedVertex[vertex[nowV][i].first] != Finish) {
				que.push(VertexDistance(vertex[nowV][i].first, vertex[nowV][i].second + nowD));
			}



		}

	}

//	cout << endl << endl;

	for (int i = 0; i < v; i++) {
		if (vertexDistance[i] == INF)
			cout << "INF" << endl;
		else
			cout << vertexDistance[i] << endl;
	}

	return 0;
}

void Init() {

	for (int i = 0; i < v; ++i) {
		vertexDistance[i] = INF;
		visitedVertex[i] = Yet;
		vertex.push_back(vector<pair<int, int> >());
	}


}




Measured memory_bytes: 15156
def biserch(l,key,flag=True):
    if flag is True:
        func = judge_1
    else:
        func = judge_2
    left = -1; right = len(l)
    while right - left > 1:
        middle = (left+right) // 2
        if func(l,key,middle) is True:
            right = middle
        else:
            left = middle
    return right

def judge_1(l,key,middle):
    if key <= l[middle]:
        return True
    else:
        return False

def judge_2(l,key,middle):
    if key < l[middle]:
        return True
    else:
        return False

N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

ans = 0
for b in B:
    top = biserch(A,b)
    bottom = N - biserch(C,b,flag=False)
    ans += top*bottom
print(ans)

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

using namespace std;
long long x[10000010], y[10000010];
#define rep(i, n) for (int i = 0; i < (n); i++)
#define lep(j, n) for (int j = 0; j < (n); j++)
#define reps(i, n) for (int i = 1; i < (n); i++)
#define leps(i, n) for (int j = 1; j < (n); j++)
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define int long long
#define gsort(x, n) sort((x), (x) + (n), greater<int>());
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
const long long mod = 1e9 + 7;

signed main()
{

   cin.tie(0);
   ios::sync_with_stdio(false);
   int a, b;
   cin >> a >> b;

   if (a >= 10 || b >= 10)
      cout << -1 << '\n';
   else if (a < 0 || b < 0)
      cout << -1 << '\n';
   else
      cout << a * b << '\n';
}

Measured memory_bytes: 256
while True:

    inputCount = int(input())

    if inputCount == 0:
        break

    timeList = [int(input()) for item in range(inputCount)]
    timeList.sort()

    totalTimeList = [0]

    for lp in range(inputCount - 1):
        waitTime = totalTimeList[-1] + timeList[lp]
        totalTimeList.append(waitTime)

    print(str(sum(totalTimeList)))



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

int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				if(a[k]<a[i]+a[j]&&a[i]!=a[j]&&a[j]!=a[k]){
					++ans;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3648
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,X = MI()
L = LI()

a = 0
ans = 1
for i in range(N):
    a += L[i]
    if a <= X:
        ans += 1

print(ans)


Measured memory_bytes: 61940
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int A, B, K;
  cin>>A>>B>>K;

  vector<int> num;
  for(int i=1;i<=min(A, B);i++)
    if(A%i == 0 && B%i == 0) num.push_back(i);

  reverse(num.begin(), num.end());
  cout<<num[K-1]<<endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string danceStep;
            danceStep = Console.ReadLine(); //標準入力

            bool odd = true;
            for (int i = 0; i < danceStep.Length; i = i + 2)
            {
                if (!(danceStep.ElementAt(i) == 'R' || danceStep.ElementAt(i) == 'U' || danceStep.ElementAt(i) == 'D'))
                {
                    odd = false;
                    break;
                }
            }

            bool gu = true;
            for (int i = 1; i < danceStep.Length; i = i + 2)
            {
                if (!(danceStep.ElementAt(i) == 'L' || danceStep.ElementAt(i) == 'U' || danceStep.ElementAt(i) == 'D'))
                {
                    gu = false;
                    break;
                }
            }

            if (odd && gu)
                Console.WriteLine("Yes");//改行付き出力
            else
                Console.WriteLine("No");//改行付き出力
        }
    }
}


Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
long long dp[1000100][4];
const int mod=1000000007;
int main()
{
	int n;
	cin>>n;
	memset(dp,0,sizeof(dp));
	dp[0][0]=8;
	dp[0][1]=1;
	dp[0][2]=1;
	dp[0][3]=0;
	for(int i=1;i<=n-1;i++)
	{
		dp[i][0]=(dp[i-1][0]*8+mod)%mod;
		dp[i][1]=(dp[i-1][0]+(dp[i-1][1]*9)%mod+mod)%mod;
		dp[i][2]=(dp[i-1][0]+(dp[i-1][2]*9)%mod+mod)%mod;
		dp[i][3]=(dp[i-1][1]+dp[i-1][2]+(dp[i-1][3]*10)%mod+mod)%mod;
	}
	cout<<dp[n-1][3]%mod<<endl;
	return 0;
}

Measured memory_bytes: 34856
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){

	int N,Q;
	while(1){int c=0;
	cin>>N;if(N==0)break;
	long long int n[4002][3]={};
	for(int i=0;i<4001;i++)
	{n[i][1]=0;n[i][2]=i;}

	for(int i=0;i<N;i++){
		long long int x,y,z;
		cin>>x>>y>>z;
		if(n[x][0]+y*z<=1000000)n[x][0]+=y*z;
		else if(n[x][0]+y*z>1000000)n[x][0]=1000000;
		if(n[x][1]==0){c++;n[x][1]=c;}
	
	}
	for(int i=0;i<4001;i++){
		for(int j=4000;j>i;j--){
			if(n[j][1]<n[j-1][1]){
				int t=n[j][0];n[j][0]=n[j-1][0];n[j-1][0]=t;
				int T=n[j][1];n[j][1]=n[j-1][1];n[j-1][1]=T;
				int TT=n[j][2];n[j][2]=n[j-1][2];n[j-1][2]=TT;
			}
		}
	}
	bool f=false;
	for(int i=0;i<4001;i++){
		if(n[i][0]>=1000000){cout<<n[i][2]<<endl;f=true;}
	}
	if(f==false)cout<<"NA"<<endl;
	
	}
	return 0;
}

Measured memory_bytes: 1268
<?php
  fscanf(STDIN, "%d %d %d", $w, $h, $n);

  $x1 = 0;
  $x2 = $w;
  $y1 = 0;
  $y2 = $h;
  
  for ($i=0; $i<$n; $i++) {
    fscanf(STDIN, "%d %d %D", $x, $y, $a);
    if ($a == 1) $x1 = max($x1, $x);
    if ($a == 2) $x2 = min($x2, $x);
    if ($a == 3) $y1 = max($y1, $y);
    if ($a == 4) $y2 = min($y2, $y);
  }      
  $dx = max(0, $x2 - $x1);
  $dy = max(0, $y2 - $y1);

  echo $dx * $dy;
?>

Measured memory_bytes: 4856
#include<iostream>

using namespace std;

int main() {
	int a[2];
	cin >> a[0] >> a[1];
	for (int i = 0; i < 2; i++) {
		if (a[i] == 1 || a[i] == 3 || a[i] == 5 || a[i] == 7 || a[i] == 8 || a[i] == 10 || a[i] == 12)a[i] = 0;
		else if (a[i] != 2)a[i] = 1;
	}
	if (a[0] == a[1])cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
<?php
define('MOD', 10 ** 9 + 7);
fscanf(STDIN, '%d', $n);

echo dfs(0, 'XXX') . PHP_EOL;

function ok($last4) {
    if (preg_match('/(AGC)|(GAC)|(ACG)|(A.GC)|(AG.C)/', $last4)) return false;
    return true;
}

function dfs($cur, $last3) {
    global $n;
    static $memo;

    if (isset($memo[$cur][$last3])) return $memo[$cur][$last3];
    if ($cur === $n) return 1;
    $ret = 0;
    foreach(['A', 'G', 'C', 'T'] as $c) {
        if (ok($last3 . $c)) $ret = ($ret + dfs($cur + 1, substr($last3, 1) . $c)) % MOD;
    }
    $memo[$cur][$last3] = $ret;
    return $ret;
}

Measured memory_bytes: 4604
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi 2*acos(0.0)
#define f first
#define s second
#define pb push_back
#define gap ' '
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mod 998244353
#define N 100005
int dp[N];
int n;
int h[N];
int solve(int i)
{
    if(i==n-1) return 0;
    if(dp[i]!=-1) return dp[i];
    int ans1=0,ans2=INT_MAX;
    ans1=abs(h[i]-h[i+1])+solve(i+1);
    if(i+2<=n-1)
    {
        ans2=abs(h[i]-h[i+2])+solve(i+2);
    }
    return dp[i]=min(ans1,ans2);

}
int main()
{
    fastio;
    cin>>n;
    for(int i=0;i<n;i++) cin>>h[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0);
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
//#pragma once
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<double,double> P;
const ll INF = 1e16;
const int MOD = 998244353;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 



///////////////////////___modpow___////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
struct SegmentTree {
private:
  int N, uni = 0;vector<int>  node;
public:
  SegmentTree(){}
  int look(int x, int y){
    return max(x, y);
  }
  void init(vector<int> v){
    int sz = v.size();
    N = 1;while(N < sz)N *= 2;
    node.resize(2*N-1, uni);

    rep(i,sz)node[i+N-1] = v[i];//最下段に値を入れる
    for(int i=N-2;i >= 0;i--)node[i] = look(node[2*i+1], node[2*i+2]);//上げていく
  }
  void update(int x, int val){
    x += (N-1);//最下段へ
    node[x] = val;
    while(x > 0){//上げていく
      x = (x-1)/2;
      node[x] = look(node[2*x+1], node[2*x+2]);
    }
  }
  int get(int a, int b, int k=0, int l=0, int r=-1){
    if(r < 0)r = N;
    if(r <= a || b <= l)return uni;
    if(a <= l && r <= b)return node[k];
    int vl = get(a, b, 2*k+1, l, (l+r)/2);
    int vr = get(a, b, 2*k+2, (l+r)/2, r);
    return look(vl, vr);
  }
};
////////////////////////////////////////////////////////////////////

int n;P x[210000];int dp[210000];
SegmentTree seg;
signed main(){
  cin>>n;
  rep(i,n)cin>>x[i].first>>x[i].second;
  sort(x, x+n);
  vector<int> v(n), xx(n);v[n-1] = n-1;
  rep(i,n)xx[i] = x[i].first;
  seg.init(v);
  for(int i = n-2;i >= 0;i--){
    int r = (lower_bound(xx.begin(), xx.end(), x[i].first+x[i].second)) - xx.begin();//はんかいくかん
    seg.update(i, r-1);
    int mx = seg.get(i, r);
    seg.update(i, mx);
  }
  int ans = 0;
  dp[n-1] = 2;
  dp[n] = 1;
  for(int i = n-2;i >= 0;i--){
    dp[i] = dp[i+1];
    int r = seg.get(i, i+1);
    dp[i] = (dp[i] + dp[r+1]) % MOD;
  }
  cout << dp[0] << endl;
}




Measured memory_bytes: 15616
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		//System.out.println("??\???>>");

		Scanner scan = new Scanner(System.in);

		int box = 3;
		int ary[];
		ary = new int[box];
		for(int i = 0; i < ary.length ; i++){

			ary[i] = scan.nextInt();
			//System.out.println(i + ":"  + ary[i]);
		}


		for(int i = 0; i < ary.length; i++ ){

			for(int j = i + 1; j < ary.length; j++){

				if(ary[i] > ary[j]){
					int temp = ary[i];
					ary[i] = ary[j];
					ary[j] = temp;
				}
			}

		}

		System.out.print(ary[0]);
		System.out.print(" ");
		System.out.print(ary[1]);
		System.out.print(" ");
		System.out.println(ary[2]);
	}

}

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

int main() {
    int n;
    cin >> n;
    map<int, int> a;
    REP(i, n) {
        int tmp_a;
        cin >> tmp_a;
        a[tmp_a] += 1;
    }
    int ans = 0;
    for(auto p : a) {
        if(p.second % 2 > 0) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4992
<?php
$input = explode(" ",  trim(fgets(STDIN)));
list($n, $m) = $input;
$A = $b = [];

for ($i = 0; $i < $n; $i++) {
    $input = explode(" ",  trim(fgets(STDIN)));
    $l = [];
    foreach ($input as $v) {
        $l[] = (int)$v;
    }
    $A[] = $l;
}

for ($i = 0; $i < $m; $i++) {
    $input = trim(fgets(STDIN));
    $b[] = (int)$input;
}

foreach ($A as $a) {
    $sum = 0;
    for ($i = 0; $i < $m; $i++) {
         $sum += $a[$i] * $b[$i];
    }
    echo $sum . "\n";
}

Measured memory_bytes: 16696
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define ff first
#define pii pair<int, int>
#define vii vector< pair<int,int> >
#define vi vector<int>
#define vvi vector< vector< int> >
#define ss second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define ull unsigned long long
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace4(x, y, z, d)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#d<<": "<<d<<endl

#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1, 0};int dy[]={0,1,0, -1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
bool compare(const pair<int,int> &a,
             const pair<int,int> &b)
{
    if(a.ff == b.ff) {
        return (b.ss < a.ss);
    }
    return (a.ff<b.ff);
}

bool prime[10000001];
void SieveOfEratosthenes(int n) 
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.

    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}

int32_t main()
{
    IOS;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    /********************* From here ***********************/
    int n;
    cin >> n;
    int cn[n] = {0};
    vector<string> v;
    int beg[n] = {0};
    int end[n] = {0};
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        v.pb(s);
    }

    for(int i=0;i<n;i++){
        string s = v[i];
        for(int j=0;j<s.length()-1;j++){
            if(s[j]=='A'&& s[j+1]=='B'){
                cn[i]++;
            }
        }
    }
    int cnt = 0;
    rep(i, 0, n){
        cnt+=cn[i];
    }
    int c1=0,c2=0,c3=0;

    rep(i, 0, n){
        if(v[i][0]=='B' && v[i][v[i].length()-1]=='A'){
            c1++;
        }
        else if(v[i][0]=='B'){
            c2++;
        }
        else if(v[i][v[i].length()-1]=='A'){
            c3++;
        }


    }

    if(c1==0){
        cout << cnt+min(c2,c3);
    }
    else{
        if(c2+c3==0){
            cout <<cnt+ c1-1;
        }
        else{
            cout <<cnt+ c1+min(c2,c3);
        }
    }
}

Measured memory_bytes: 1024
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define PI 3.141592653589793
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define mem(x, a) memset(x, a, sizeof x)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pcl pair<char, ll>
#define psl pair<string, ll>


ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
unordered_map<ll, ll> mp;
set<ll> s;
string S = "";
ll cases;

int main() {
	go;
    cin >> N;
    if(N < 1200) {
    	cout << "ABC\n";
    }
    else {
    	cout << "ARC\n";
    }
    
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 3604
A = []
B = []
ans = []
n,m,l = map(int, input().split())
for i in range(n):
    elem = list(map(int,input().split()))
    A.append(elem)
for i in range(m):
    elem = list(map(int, input().split()))
    B.append(elem)

for i in range(n):
    ans = []
    for j in range(l):
        calc = 0
        for k in range(m):
            calc += A[i][k] * B[k][j]
        ans.append(calc)
    for s in range(l):
        if s == l - 1:
            print(ans[s])
        else:
            print(ans[s], end=' ')
        


Measured memory_bytes: 6572
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int h[30];
int main(){
	int n;cin>>n;
	rep(i,n)cin>>h[i];
	int cnt=0;
	rep(i,n){
		bool ok=true;
		for(int j=0;j<i;j++){
			if(h[j]>h[i])ok=false;
		}
		if(ok)cnt++;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

const int N = 50005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int n;
map <int,int> mp;

int main(){
    cin>>n;
    int answ = 0;
    while(n--){
        int a;
        cin>>a;
        if(mp[a] == 0)
            answ++;
        else
            answ--;
        mp[a] = 1 - mp[a];
    }
    cout<<answ<<endl;
    return 0;
}


Measured memory_bytes: 4992
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int A[100010];
    REP(i,N) cin >> A[i];
    int flag = 0;
    REP(i,N){
        if (A[i] % 2 == 1){
            flag += 1;
        }
    }
    if (flag % 2 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int k = sc.nextInt();
			int p[] = new int[n];
			int sum = 0;
			for(int i = 0; i < p.length; i++) {
				p[i] = sc.nextInt();
			}
			Arrays.sort(p);
			for(int i = 0; i < k; i++) {
				sum += p[i];
			}
			System.out.println(sum);
	}

}

Measured memory_bytes: 30176
D,G = map(int,input().split())
p,c = [],[]
for i in range(D):
    s,t = map(int,input().split())
    p.append(s)
    c.append(t)

ans = float('inf')
for i in range(2**D):
    pnt = 0
    cnt = 0
    for j in range(D):
        if ((i >> j) % 2 == 1):
            pnt += p[j]*100*(j+1)+c[j]
            cnt += p[j]
        else:
            unsolved = j
    if pnt >= G:
        ans = min(ans,cnt)
    elif pnt + (p[unsolved]-1)*100*(unsolved+1) >= G:
        if G-pnt < 100*(unsolved+1):
            tmp = 1
        else:
            tmp = (G-pnt)//(100*(unsolved+1))
        ans = min(ans,cnt+tmp)
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<climits>

using namespace std;

int main(){
	int n, t;
	int *a;

	cin>> n>> t;
	a= new int[n];

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

	int minA[n];
	int profit[n];

	minA[0]= a[0];
	profit[0]= -a[0];

	for(int i=1; i<n; i++) minA[i]= min(minA[i-1], a[i]);
	for(int i=1; i<n; i++) profit[i]= a[i]-minA[i-1]; 

	int maxProfit= INT_MIN;
	int numMax=0;
	for(int i=0; i<n; i++) maxProfit= max(maxProfit, profit[i]);
	for(int i=0; i<n; i++){
		if(profit[i] == maxProfit) numMax++;			
	}

	cout<< numMax<< endl;

	return 0;	
}

Measured memory_bytes: 1408
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut n: i32 = read();
    println!("{}", if n == 0 { String::from("0") } else {
        let mut s = vec![];
        loop {
            s.push(if n % 2 != 0 { 1 } else { 0 });
            if n % 2 != 0 { n -= 1; }
            n /= -2;
            if n == 0 { break; }
        }
        s.reverse();
        s.into_iter().map(|d| std::char::from_digit(d, 10).unwrap()).collect()
    });
}

Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main(void){
  int i,j,k,c,n;
  string s;
  vector <int> v;
  int a[27],b[27];
  
  cin>>n;
  cin>>s;
  
  for(i=1;i<n;i++){
    for(k=0;k<28;k++){
    a[k]=0;
    b[k]=0;
  }
    c=0;
    for(j=0;j<i;j++){
      a[s[j]-97]++;
    }
    for(;j<n;j++){
      b[s[j]-97]++;
      
    }
    for(j=0;j<26;j++){
     if(a[j]>0&&b[j]>0)
        c++;
    }
    v.push_back(c);
  }
  sort(v.begin(),v.end(),greater<int>());
   cout<<v[0]<<endl;
  return 0;
}

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

int N;

struct point{
	char c; //
	int i;
	point(char cc, int ii) {
		c = cc;
		i = ii;
	}
};

int main() {
	//freopen("data.txt", "r", stdin);
	cin >> N;
	string S; cin >> S;
	vector<point> v;
	for (int i = 0; i < S.size(); ++i) {
		point p(S[i], i);
		if ( v.size() && v.back().c == '(' && S[i] == ')') {
			v.pop_back();
		}
		else {
			v.emplace_back(S[i], i);
		}
	}
	int a = 0, b = 0;
	for (int i = 0; i < v.size(); ++i) {
		if (v[i].c == '(') ++a;
		else ++b;
	}
	string res = string(b, '(') + S + string(a, ')');
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9+7;

ll fact[100010];
ll rfact[100010];

ll a[100010];
ll dp[100010];

void init() {
  fact[0] = 1;
  for(int i = 1;i < 100010;++i){
    fact[i] = (fact[i-1] * i) % mod;
  }
  ll x = fact[100009];
  ll p = mod-2;
  ll acc = 1;
  while(p > 0){
    if(p & 1) {
      acc = (acc * x) % mod;
    }
    x = (x * x) % mod;
    p >>= 1;
  }
  rfact[100009] = acc;
  for(int i = 100009;i > 0;--i){
    rfact[i-1] = (rfact[i] * i) % mod;
  }
}

ll nck(ll n, ll k) {
  ll acc = 1;
  acc = (acc * fact[n]) % mod;
  acc = (acc * rfact[k]) % mod;
  acc = (acc * rfact[n-k]) % mod;
  return acc;
}

int main(void){
  init();
  int n;
  cin >> n;
  for(int i = 1;i <= n;++i){
    cin >> a[i];
  }
  dp[1] = 1;
  for(int i = 2;i <=n;++i){
    dp[i] = (dp[i-1] * i) % mod;
    dp[i] = (dp[i] + fact[i-1]) % mod;
  }
  for(int i = 1;i <= n;++i){
    dp[i] = (dp[i] - fact[i] + mod) % mod;
    dp[i] = (dp[i] * nck(n, i)) % mod;
    dp[i] = (dp[i] * fact[n-i]) % mod;    
  }
  ll res = 0;
  for(int i = 1;i <= n;++i){
    ll diff1 = (dp[i] * a[i]) % mod;
    res = (res + diff1) % mod;
    ll diff2 = (dp[n-i+1] * a[i]) % mod;
    res = (res + diff2) % mod;
    ll diff3 = (fact[n] * a[i]) % mod;
    res = (res + diff3) % mod;
  }
  cout << res << endl;
  return 0;
}



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

struct CycleDetection{
    vector<vector<int>> G;
    vector<int> seen,finished;
    stack<int> hist;
    int pos;
    CycleDetection(int n):G(n),seen(n,0),finished(n,0),pos(-1){}
    void add_edge(int u,int v){
        G[u].emplace_back(v);
    }
    void dfs(int v){
        seen[v]=1; hist.push(v);
        for (int u:G[v]){
            if (finished[u]) continue;
            if (seen[u]&&!finished[u]){pos=u; return;}
            dfs(u);
            if (pos!=-1) return;
        }
        finished[v]=1; hist.pop();
    }
    vector<int> build(int &cycle){
        for (int v=0;v<G.size();++v){
            if (!seen[v]) dfs(v);
        }
        cycle=(pos!=-1);
        vector<int> res;
        while(!hist.empty()){
            int t=hist.top(); hist.pop();
            res.emplace_back(t);
            if (t==pos) break;
        }
        return res;
    }
};

void GRL_4_A(){
    int V,E; cin >> V >> E;
    CycleDetection CD(V);
    for (;E--;){
        int s,t; cin >> s >> t;
        CD.add_edge(s,t);
    }
    int ans;
    CD.build(ans);
    cout << ans << '\n';
}

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


Measured memory_bytes: 3240
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


ll n, m, cnt[110000], s1[110000], s2[110000], ans;

void f(ll i, ll mn) {
	ll now = mn;
	now -= min(now, s2[i]);
	s1[i] -= min(now, s1[i]);
	ans += s1[i] / 2;
}
int main() {
	cin >> n >> m;
	REP(i, n) {
		ll a;
		cin >> a;
		cnt[a]++;
	}
	REP(i, 110000) {
		if (cnt[i] % 2 == 1)s2[i % m]++;
		s1[i % m] += cnt[i] - cnt[i] % 2;
	}
	REPO(i, (m - 1) / 2) {
		ll mn = min(s1[i] + s2[i], s1[m - i] + s2[m - i]);
		ans += mn;
		f(i, mn);
		f(m - i, mn);
	}
	ans += (s2[0] + s1[0]) / 2;
	if (m % 2 == 0)ans += (s2[m / 2] + s1[m / 2]) / 2;
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map> 
#include<fstream> 
using namespace std;
#define mid 1000000007
 map<int,int>c;
int main(){
	int k=1,sum=0,ans=0,i;
	string s;
	cin>>s;
	int a=s.size();
	for(i=a-1;i>=0;i--){//注意是从后先前取 
		sum=((s[i]-'0')*k+sum)%2019;
		c[sum]++;
		k=(k*10)%2019;
	}
	for(i=0;i<2019;i++){
		if(i==0)
		ans+=c[i];
		if(c[i]>=2)
		ans+=c[i]*(c[i]-1)/2; 
	}
	cout<<ans;
} 

Measured memory_bytes: 3736
// Why am I so dumb? :c
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)1e5 + 5;

int arr[MAXN];

int n, mn, mx;

void print(bool x) {
    printf(x ? "Yes\n" : "No\n");
}

bool calc(int x) {
    int cnt = 0, cnt2 = 0;

    for (int i = 1; i <= n; ++i) {
        if (arr[i] == x) {
            ++cnt;
        }
        else {
            ++cnt2;
        }
    }

    int left = x - cnt2;

    if (left < 0 || (left == 0 && cnt > 0)) {
        return 0;
    }

    return cnt >= left * 2;
}

void solve() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }

    mn = mx = arr[1];

    for (int i = 2; i <= n; ++i) {
        mn = min(mn, arr[i]);
        mx = max(mx, arr[i]);
    }

    if (mx - mn > 1) {
        print(0);
        return;
    }

    if (mn == mx) {
        print(mx * 2 <= n || mx + 1 == n);
    }
    else {
        print(calc(mx));
    }
}

int main() {
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 640
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <numeric>
using namespace std;

int main(){

        string S;
        cin>>S;
        for(int i=0;i<S.size();i++) {
            if (S[i]=='?')
                S[i]='D';
        }
        cout<< S<< endl;
    
}


Measured memory_bytes: 3364
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()


def solve():
    x = ini()
    lb, ub = 0, 0
    while lb <= x:
        if lb <= x <= ub:
            return True
        lb += 100
        ub += 105
    return False


print(1 if solve() else 0)


Measured memory_bytes: 9188
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int dp;
vector<int> dp2(1LL<<26, 1e9);
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s; cin >> s;
  int x = 0;
  dp = dp2[0] = 0;
  FOR(i,0,s.length()) {
    x ^= 1LL << (s[i] - 'a');
    int m = dp2[x];
    FOR(j,0,26) {
      m = min(m, dp2[x^(1LL<<j)]);
    }
    dp2[x] = min(dp2[x], m + 1);
    dp = m + 1;
  }
  cout << dp << endl;
  return 0;
}

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

int main()
{
	int n;
	int x;
	cin >> n >> x;
	vector<int> m;
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		m.push_back(k);
		x -= k;
	}
	sort(m.begin(), m.end());
	int enable;
	enable = x / m[0] + n;
	cout << enable;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define S_MAX 8
using namespace std;

class State {
public:
  int x, y, hp, t;
  State(int x, int y, int hp, int t) : x(x), y(y), hp(hp), t(t) {}
  bool operator <(const State &s) const {
    if(x != s.x) return x < s.x;
    if(y != s.y) return y < s.y;
    return hp < s.hp;
  }
};

int w, h;
int M[S_MAX][S_MAX];
int sx, sy;

void solve() {
  queue<State> que;
  set<State> vis;
  State s(sx, sy, 6, 0);
  const int dx[4] = {1,0,-1,0};
  const int dy[4] = {0,1,0,-1};
  que.push(s);
  vis.insert(s);
  while(!que.empty()) {
    s = que.front(); que.pop();
    if(M[s.y][s.x] == 3) {
      cout << s.t << endl;
      return;
    } else if(M[s.y][s.x] == 4) {
      s.hp = 6;
    }
    if(s.hp <= 1) continue;
    for(int i = 0; i < 4; ++i) {
      int nx = s.x + dx[i];
      int ny = s.y + dy[i];
      if(nx < 0 || nx >= w) continue;
      if(ny < 0 || ny >= h) continue;
      if(M[ny][nx] == 0) continue;
      State ns(nx, ny, s.hp-1, s.t+1);
      if(vis.find(ns) != vis.end()) continue;
      vis.insert(ns);
      que.push(ns);
    }
  }
  cout << -1 << endl;
}

main() {
  while((cin >> w >> h) && (w || h)) {
    for(int i = 0; i < h; ++i) {
      for(int j = 0; j < w; ++j) {
	cin >> M[i][j];
	if(M[i][j] == 2) {
	  sx = j;
	  sy = i;
	  M[i][j] = 1;
	}
      }
    }
    solve();
  }
}

Measured memory_bytes: 0
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    S = list(input())
    N = len(S)
    
    d = defaultdict(int)
    d[0] = 1
    ans = 0
    tmp = 0
    for i in range(N):
        si = int(S[N - 1 - i])
        tmp = (tmp + si * pow(10, i, 2019)) % 2019
        ans += d[tmp]
        d[tmp] += 1
    print(ans)


if __name__ == '__main__':
    solve()


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

int main(void) {
    string n;
    int zohe = 0;
    cin >> n;
    for (int i = 0; i < n.size(); i++) zohe += (int)(n[i] - '0');
    cout << (stoi(n) % zohe ? "No" : "Yes") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll N = 1e5 + 5, MOD = 1e9+7;

ll r,d,x;
ll dp[N];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>r>>d>>x;

    dp[1]=r*x-d;

    for( ll i=2; i<=10; i++){
        dp[i]=dp[i-1]*r-d;
    }

    for( ll i=1; i<=10; i++ )       cout<<dp[i]<<endl;
    return 0;
}




Measured memory_bytes: 256
import numpy as np
N = int(input())
h = list(map(int, input().split()))

dp = np.full(N, np.inf)
dp[0] = 0
for i in range(1,N):
  dp[i] = min(dp[i],dp[i-1]+np.abs(h[i] - h[i-1]))
  if i > 1: dp[i] = min(dp[i],dp[i-2]+np.abs(h[i] - h[i-2]))
print(int(dp[-1]))

Measured memory_bytes: 22688
#include <stdio.h>

int main()
{
	int n, divisor, count = 0;
  	scanf("%d", &n);
  	for (int i = 105; i <= n; i += 2){
      	divisor = 0;
    	for (int j = 1; j <= i; j += 2){
        	if(i % j == 0){
            	divisor++;
            }
        }
      	if (divisor == 8){
        	count++;
        }
    }
  	printf("%d", count);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    string s;
    cin >> s;
    cout << s.substr(0, 3) << endl;

}



Measured memory_bytes: 3600
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}
func bOut(f bool, x string, y string) {
	if f {
		fmt.Println(x)
	} else {
		fmt.Println(y)
	}
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	x, y := make([]float64, n), make([]float64, n)
	for i := 0; i < n; i++ {
		x[i], y[i] = fScan(), fScan()
	}
	p, q, r, s := 0., 0., 1000., 1000.
	w := 250.
	ans := float64(mod)
	z := 100
	for {
		np, nq, nr, ns := 0., 0., 0., 0.
		a := float64(mod)
		for i := 0; i <= z; i++ {
			for j := 0; j <= z; j++ {
				fi := float64(i)
				fj := float64(j)
				u, v := p+(r-p)*fi/float64(z), q+(s-q)*fj/float64(z)
				d := 0.
				for i := 0; i < n; i++ {
					d = flarger(d, (u-x[i])*(u-x[i])+(v-y[i])*(v-y[i]))
				}
				if d < a {
					a = d
					np, nq, nr, ns = u-w, v-w, u+w, v+w
				}
			}
		}
		p, q, r, s = np, nq, nr, ns
		ans = a
		if w < 1e-8 {
			break
		}
		w = w / 2
	}
	fmt.Println(math.Pow(ans, 0.5))
}
func flarger(a, b float64) float64 {
	if a < b {
		return b
	} else {
		return a
	}
}


Measured memory_bytes: 1796