akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    long long a,b;
    cin >> a >> b;
    long long v = __gcd(a,b);
    long long ans = 1;
    for(long long i = 2 ; i <= sqrt(v) ; i += 1){
        bool t = false;
        while(v%i == 0){
            v /= i;
            if(!t){
                ans += 1;
            }
            t = true;
        }
    }
    if(v > 1){
        ans += 1;
    }
    cout << ans;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<map>
#define p 13331
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
map<unsigned long long,int>mp;
char ss[20];
int cnt[30];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n=read();long long ans=0;
    for(int i=1;i<=n;i++)
    {
    	scanf("%s",ss+1);memset(cnt,0,sizeof(cnt));
    	for(int j=1;j<=10;j++)cnt[ss[j]-'a'+1]++;
    	unsigned long long uf=0;
    	for(int j=1;j<=26;j++)uf=uf*p+cnt[j];
    	if(mp.find(uf)==mp.end())mp[uf]=1;
    	else ans+=mp[uf],mp[uf]++;
    }printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 6528
import scala.io.{StdIn => in}

object Main extends App {
  val Array(n, m) = in.readLine.split(" ").map(_.toInt)

  val (l, r) = Iterator.continually(in.readLine)
    .take(m)
    .map(_.split(" ").map(_.toInt))
    ./:((1, n)) { case ((l, r), e) =>
      (l max e(0), r min e(1))
    }

  val ans = (1 + r - l) max 0
  println(ans)
}

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

char s[50][50];

int main(void){
	int h, w;
	cin >> h >> w;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin >> s[i][j];
		}
	}
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			int a=0;
			if(s[i][j]=='#'){
				if(i-1>0&&s[i-1][j]=='.'||i==0) a++;
				if(i+1<h&&s[i+1][j]=='.'||i==h-1) a++;
				if(j-1>0&&s[i][j-1]=='.'||j==0) a++;
				if(j+1<w&&s[i][j+1]=='.'||j==w-1) a++;
				if(a==4){
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
N,C,K = map(int,input().split())
T = []
for i in range(N):
  T.append(int(input()))

T.sort()
counter = 0
while len(T) > 0:
  if len(T) == 1:
    T.pop()
    counter += 1
  else:
    c = 1
    while c <= len(T)-1 and c < C:
      if T[c] - T[0] <= K:
        c += 1
      else:
        break
  
    del T[:c]
    counter += 1

print(counter)

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define repp(i, start, to) for (li i = (li)(start); i < ((li)(to)); i++)

int main(void)
{
	li x;
	cin >> x;

	li res = 1;
	for (li b = 2; b <= sqrt(x); b++) {
		for (li bp = b * b; bp <= x; bp *= b) {
			res = max(res, bp);
		}
	}
	cout << res << endl;

	return 0;
}

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		List<Integer> p = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			p.add(sc.nextInt());
		}
		Collections.sort(p);
		int s = p.subList(0, K).stream().mapToInt(i -> i).sum();
		System.out.println(s);
	}

}


Measured memory_bytes: 39208
package main

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

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var k, n int
	var a int
	var A []int
	fmt.Fscan(r, &k, &n)
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a)
		A = append(A, a)
	}

	//	fmt.Fprintln(w, getMaxHappy(x))
	var d []int
	for i := 0; i < n; i++ {
		var di int
		if i == n-1 {
			di = k - A[i] + A[0]
		} else {
			di = A[i+1] - A[i]
		}
		d = append(d, int(math.Abs(float64(di))))
	}

	// find max value mi is max value id
	m := 0
	mi := 0
	for i := 0; i < n; i++ {
		if d[i] > m {
			m = d[i]
			mi = i
		}
	}

	// sum d without max value
	result := 0
	for i := 0; i < n; i++ {
		if i == mi {
			continue
		}
		result += d[i]
	}

	fmt.Fprintln(w, result)
}

Measured memory_bytes: 10112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e18)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
#define YesNo(a) cout<<TO((a),"Yes","No")<<endl;


ll maxSubarrayXOR(vector<ll> set,ll n){
	// https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/
	const ll INT_BITS = 64;
	ll index = 0;
	for(ll i=INT_BITS-1;i>=0;i--){
		ll maxInd = index;
		ll maxEle = -INF;
		for(ll j=index; j<n; j++){
			if( (set[j] & (1LL<<i))!=0
				&& set[j] > maxEle)
			{
				maxEle = set[j];
				maxInd = j;
			}
		}
		if(maxEle == -INF)continue;
		swap(set[index],set[maxInd]);
		maxInd = index;
		for(ll j=0;j<n;j++){
			if( j!=maxInd && ((set[j]&(1LL<<i))!=0) ){
				set[j] = set[j]^set[maxInd];
			}
		}
		index++;
	}
	ll res = 0;
	for(ll i=0;i<n;i++){
		res ^= set[i];
	}
	return res;
}



int main(){
	ll N,AX=0;
	cin >> N;
	vector<ll> A(N),B(N);
	FOR(i,0,N)cin>>A[i], AX^=A[i];
	FOR(i,0,N)B[i] = A[i]-(AX&A[i]);
	ll ans = maxSubarrayXOR(B,N);
	cout << ans+(AX^ans) << endl;
}



Measured memory_bytes: 2560
import java.util.Scanner;

class Main{
	
	static int getAns(int[] r,int[] c,int n){
		int[][] dp=new int[n][n];
		
		for(int i=0;i<n;i++)
			for(int j=i;j<n;j++)
				dp[i][j]=Integer.MAX_VALUE;
		
		
		int i=0; int j=0;
		
		for(int sj=0;sj<n;sj++){
			i=0; j=sj;
			for(int k=0;k<n-sj;k++){
				if(i==j)
					dp[i][j]=0;
				else{
					for(int m=i;m<j;m++){
						dp[i][j]=Math.min(dp[i][j],dp[i][m]+dp[m+1][j]+r[i]*c[m]*c[j]);
					}
				}
				i++; j++;
			}
		}
		
		
		return dp[0][n-1];
	}
				
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		int[] r=new int[n];
		int[] c=new int[n];
		
		for(int i=0;i<n;i++){
			r[i]=scan.nextInt();
			c[i]=scan.nextInt();
		}
		
		System.out.println(getAns(r,c,n));
		
	}
}
		


Measured memory_bytes: 26812
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,l,r,d,ch[100000],loc[100000];
typedef pair<ll,ll>P;
int main(void){
    cin>>n>>m;
    vector<vector<P>>v(n);
    for(int i=0;i<m;i++){
        cin>>l>>r>>d;
        r--;
        l--;
        v[l].push_back({r,d});
        v[r].push_back({l,-d});
    }
    for(ll i=0;i<n;i++){
        if(!ch[i]){
            ch[i]++;
            queue<ll>que;
            que.push(i);
            while(!que.empty()){
                ll q=que.front();
                que.pop();
                for(auto x:v[q]){
                    
                    if(!ch[x.first]){
                        loc[x.first]=loc[q]+x.second;
                        ch[x.first]++;
                        que.push(x.first);
                    }
                    else{
                        if(loc[x.first]!=loc[q]+x.second){cout<<"No"<<endl;return 0;}
                    }
                }
                
            }
        }
    }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 14848
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k;
    cin>>n>>k;
    if(n*500>=k)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
'use strict'

const main = (input) => {
    input = input.split('\n')
    let temp = input[0].split(' ')
    const N = parseInt(temp[0])
    const L = parseInt(temp[1])
    const strs = input.slice(1, N + 1)
    strs.sort()
    console.log(strs.reduce((sum, v) => sum += v))
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

Measured memory_bytes: 7500
using System;
using System.Linq;
using System.Collections.Generic;
using System.Collections;
public class Program {
  public static void Main() {
    int N = ReadInt();
    int[] A = SpecialRead(), B = SpecialRead(), C = SpecialRead();
    Console.WriteLine(Complement(A, 1, N).Intersect(C).Union(B.Intersect(C)).Distinct().Count());
  }

  private static int[] SpecialRead() {
    return Console.ReadLine().Split(' ').Select(int.Parse).Skip(1).ToArray();
  }

  private static int[] Complement(int[] A, int a, int b) {
    int[] notA = new int[(b-a+1) - A.Length];
    for (int i = a, j = 0; i <= b; i++) {
      if (!A.Contains(i)) {
        notA[j] = i;
        j++;
      }
    }
    return notA;
  }

  private static int ReadInt() { return int.Parse(Console.ReadLine()); }
  private static double ReadDouble() { return double.Parse(Console.ReadLine()); }
  private static long ReadLong() { return long.Parse(Console.ReadLine()); }
  private static char ReadChar() { return Console.ReadLine()[0]; }
  private static string[] ReadStringArray() { return Console.ReadLine().Split(' '); }
  private static int[] ReadIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
  private static double[] ReadDoubleArray() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
  private static long[] ReadLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
  private static char[] ReadCharArray() { return Console.ReadLine().ToArray(); }
}



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

int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int curMin = 1e9;
  int ans = 0;
  rep(i,n) {
    curMin = min(curMin, p[i]);
    if (curMin == p[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1152
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

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

const int N = 2e5 + 10;

vector<int> g[N];
bool win[N];
int dist[N];

int bfs(int s, int n);

int main() {
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	int t = bfs(1, n);
	t = bfs(t, n);
	int d = dist[t] + 1;
	win[1] = true;
	win[2] = false;
	for (int i = 3; i <= d; ++i) {
		win[i] = (!win[i - 1] or !win[i - 2]);
	}
	if (win[d]) {
		cout << "First\n";
	} else {
		cout << "Second\n";
	}
}

int bfs(int s, int n) {
	for (int i = 1; i <= n; ++i) {
		dist[i] = n + 1;
	}
	dist[s] = 0;
	queue<int> q;
	q.push(s);
	int t = s;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		t = u;
		for (auto &v : g[u]) {
			if (dist[u] + 1 < dist[v]) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	return t;
}

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

    using namespace std;

#define ll long long

int Time[100200];
int T, N;
int x, y;

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

    cin >> N >> T;

    for(int i=0; i<N; i++){
        cin >> x >> y;
        Time[x+1]++;
        Time[y+1]--;
    }

    for(int i=1; i<T+4; i++){
        Time[i] = Time[i-1] + Time[i];
    }

    int MAX = 0;


    for(int i=1; i<T+4; i++){
        MAX = max(MAX,Time[i]);
    }

    cout << MAX << "\n";
    return 0;
}



Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

const int MOD = 998244353;

int main(){
    string S; cin >> S;
    int K; cin >> K;
    vector<int> seg;
    int cnt = 0;
    for(int i=S.size()-1;i>=0;i--){
        if(S[i] == '0'){
            seg.push_back(cnt);
            cnt = 0;
        } else {
            cnt++;
        }
    }
    seg.push_back(0);
    K = min(K, accumulate(seg.begin(), seg.end(), 0));
    vector dp = vector(seg.size(), vector(K+1, vector(K+1, 0LL)));
    dp[0][0][0] = 1;
    int upper = 0;
    for(int i=0;i+1<seg.size();i++){
        for(int hold=0;hold<=upper;hold++){
            for(int op=0;op<=upper;op++){
                for(int j=0;j<=hold;j++){
                    dp[i+1][hold-j][op] = (dp[i+1][hold-j][op] + dp[i][hold][op]) % MOD;
                }
                for(int j=1;j<=min(seg[i], K-max(hold,op));j++){
                    dp[i+1][hold+j][op+j] = (dp[i+1][hold+j][op+j] + dp[i][hold][op]) % MOD;
                }
            }
        }
        upper = min(upper + seg[i], K);
    }
    long long res = 0;
    for(int i=0;i<=K;i++){
        for(int j=0;j<=K;j++){
            res = (res + dp.back()[i][j]) % MOD;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 30220
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
const double pi = acos(-1);
const double EPS = 1e-10;

int main(){
  int n,t;
  cin >> n >> t;
  vector<pii> c(n);
  REP(i,n) cin >> c[i].first >> c[i].second;
  sort(ALL(c));
  REP(i,n){
    if (c[i].second <= t) {
      cout << c[i].first << endl;
      break;
    }else if(i == n-1){
      cout << "TLE" << endl;
    }
  }
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a[5];
    rep (i, 5) {
        cin >> a[i];
    }

    int mi = INF;
    int index = 0;
    rep (i, 5) {
        if (a[i]%10!=0) {
            if (a[i]%10 < mi) {
                mi = a[i]%10;
                index = i;
            }
        }
    }

    int ans = 0;
    if (mi == INF) {
        rep (i, 5) {
            ans += a[i];
        }
    } else {
        rep (i, 5) {
            if (i == index) {
                ans += a[i];
            } else {
                if (a[i]%10 == 0) {
                    ans += a[i];
                } else {
                    ans += (a[i]/10)*10+10;
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>

int main()
{
	std::string s;
	std::cin >> s;
	
	int c = 0;
	int max = 0;
	for (char e : s) {
		if (e == 'R') {
			c++;
		}
		else {
			max = std::max(max, c);
			c = 0;
		}
	}
	
	std::cout << std::max(max, c) << std::endl;
	
	return 0;
}


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	const uint64_t MOD = 998244353;
	int N, K;
	cin >> N >> K;
	vector<uint64_t> dp1(N + 1), dp2(N+1);
	vector<pair<int, int> > lr(K);
	for (auto& a : lr)
	{
		cin >> a.first >> a.second;
	}
	dp1[1] = 1;
	dp2[2] = 1;
	uint64_t curr = 0;
	forn(i, N) 
	{
		curr = (curr + dp1[i] + MOD - dp2[i]) % MOD;
		if(curr == 0)
			continue;
		for (const auto& a : lr)
		{
			if (i + a.first <= N)
				dp1[i + a.first] = (dp1[i + a.first] + curr) % MOD;
			if (i + a.second + 1 <= N)
				dp2[i+a.second + 1] = (dp2[i+a.second + 1] + curr) % MOD;
		}
	}
	cout << (curr + dp1[N] + MOD - dp2[N]) % MOD << endl;
	return 0;
}


Measured memory_bytes: 6356
N = int(input())
A = list(map(int, input().split()))
count = 0
flag = ''

while True:
    for index, a in enumerate(A):
        if a % 2 != 0:
            flag = 'true'
        A[index] = A[index] / 2
    if flag == 'true':
        break
    count += 1

print(count)

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

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int a, b;
    cin >> a >> b;
    if (a <= 0 && b >= 0) {
        cout << "Zero\n";
        return 0;
    }
    bool s = 1;
    s ^= (max(0, -a) & 1);
    s ^= (max(0, -b + 1) & 1);
    if (s) cout << "Positive\n";
    else cout << "Negative\n";
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>

using namespace std;

int a[85][85];
int b[85][85];
int c[85][85];
bool dp[85][85][10000];

int main()
{
  int h, w; cin >> h >> w;
  for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j) cin >> a[i][j];
  for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j) cin >> b[i][j];
  for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j) c[i][j] = abs(a[i][j]-b[i][j]);
  
  dp[1][1][c[1][1]] = true;
  
  for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j)
    for (int k = 0; k < 9000; ++k) if (dp[i][j][k]) {
      dp[i+1][j][k+c[i+1][j]] = true;
      dp[i+1][j][abs(k-c[i+1][j])] = true;
      dp[i][j+1][k+c[i][j+1]] = true;
      dp[i][j+1][abs(k-c[i][j+1])] = true;
    }
  
  for (int i = 0; i < 100; ++i) if (dp[h][w][i]) {
    cout << i << endl; return 0;
  }
}

Measured memory_bytes: 68736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
const ll MOD=1000000007,MOD2=998244353,INF=1e18;

//MODをとるパターン
ll modpower(ll n,ll p){
    if(p==0){return 1;}
    if(p%2==1){return n*modpower(n,(p-1)/2)%2019*modpower(n,(p-1)/2)%2019;}
    else{return modpower(n,p/2)*modpower(n,p/2)%2019;}
}

int main() {
    string S;
    cin>>S;
    reverse(S.begin(),S.end());
    int N=sz(S);
    vector<int> amari(N);
    int x=0;
    rep(i,N){
        x+=(S.at(i)-'0')*modpower(10,i)%2019;
        x%=2019;
        amari.at(i)=x;
//cout<<x<<" ";
    }
    amari.pb(0);
    sort(amari.begin(),amari.end());
    ll count=1,ans=0;
    rep(i,N){
        if(amari.at(i+1)==amari.at(i)){
            count++;
        }
        else{
            ans+=count*(count-1)/2;
            count=1;
        }
    }
    ans+=count*(count-1)/2;
    cout<<ans<<endl;
    //rep(i,N)cout<<amari.at(i)<<" ";
}


Measured memory_bytes: 5244
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000
#define MAX 200001

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const ll MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    COMinit();
    ll S;
    cin >> S;
    ll N = S / 3;
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        if(i == 1){
            ans++;
            continue;
        }
        ll now_s = S - (i*3);
        ans += COM(now_s+i-1,i-1);
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
#define ll long long int
#define ss second
#define ff first
#define Mem(x,val) memset(x,val,sizeof x)
#define pb push_back
#define all(v) v.begin(),v.end()
#define unik(v)  v.erase(unique(v.begin(),v.end()),v.end())
#define cerr(x) cerr << __LINE__ << " th Line : " << #x << " = " << x << "\n"
using namespace std;
typedef pair<int, int> pii;
const ll mod = 998244353;
const ll sz = 2 * 1e6 + 10, inf = 1e12 + 10;

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

	int n; string s;
	cin >> n >> s;
	ll r = 0, g = 0, b = 0;
	for (char ch : s)
		if (ch == 'R')r++;
		else if (ch == 'G')g++;
		else b++;

	ll ans = r * b * g;
	for (int i = 0; i < n ; i++)
	{
		for (int j = i + 1; j < n; j++) {
			int k = 2 * j - i;
			if (k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i])ans--;
		}
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 3592
C = input()
if C=='a':
    print('b')
elif C=='b':
    print('c')
elif C=='c':
    print('d')
elif C=='d':
    print('e')
elif C=='e':
    print('f')
elif C=='f':
    print('g')
elif C=='g':
    print('h')
elif C=='h':
    print('i')
elif C=='i':
    print('j')
elif C=='j':
    print('k')
elif C=='k':
    print('l')
elif C=='l':
    print('m')
elif C=='m':
    print('n')
elif C=='n':
    print('o')
elif C=='o':
    print('p')
elif C=='p':
    print('q')
elif C=='q':
    print('r')
elif C=='r':
    print('s')
elif C=='s':
    print('t')
elif C=='t':
    print('u')
elif C=='u':
    print('v')
elif C=='v':
    print('w')
elif C=='w':
    print('x')
elif C=='x':
    print('y')
elif C=='y':
    print('z')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
typedef long long ll;
typedef vector<int> vi;
typedef unsigned long ul;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef set<int> si;
typedef multiset<int> mi;
 
const ll INF = 1e18;
const int MOD = 1e9+7;
 
int main() {
	
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	//ofstream cout ("fileName.txt");
	//ifstream cin ("fileName.txt");
 	
	ll n;
	cin>>n;
	string s;
	
	while(n) {
		--n;
		s+='a'+char(n%26);
		n/=26;
	}
	
	reverse(s.begin(),s.end());
	cout<<s<<"\n";

	return 0;
}


Measured memory_bytes: 3656
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

#define H_MAX 2005
#define W_MAX 2005

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	char table[H_MAX][W_MAX + 10];
	pair<int,int> xypoint[H_MAX*W_MAX], yxpoint[H_MAX*W_MAX];
	
	int H, W; scanf("%d%d", &H, &W);
	int tail = 0;
	for (int i = 0; i < H; i++){
		scanf("%s", table[i]);
		for (int j = 0; j < W; j++){
			if ('#' == table[i][j]){
				yxpoint[tail] = make_pair(i, j);
				xypoint[tail] = make_pair(j, i);
				tail++;
			}
		}
	}

	for (int i = 0; i < W; i++){
		xypoint[tail] = make_pair(i, -1);
		xypoint[tail+1] = make_pair(i, H);
		yxpoint[tail] = make_pair(-1, i);
		yxpoint[tail+1] = make_pair(H, i);
		tail += 2;
	}
	for (int i = 0; i < H; i++){
		xypoint[tail] = make_pair(-1, i);
		xypoint[tail+1] = make_pair(W, i);
		yxpoint[tail] = make_pair(i, -1);
		yxpoint[tail+1] = make_pair(i, W);
		tail += 2;
	}

	sort(xypoint, xypoint + tail);
	sort(yxpoint, yxpoint + tail);

	int ret = 0;
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			if ('.' == table[i][j]){
				int xindex = lower_bound(xypoint, xypoint + tail, make_pair(j, i)) - xypoint;
				int yindex = lower_bound(yxpoint, yxpoint + tail, make_pair(i, j)) - yxpoint;
				ret = max(ret, (xypoint[xindex].second - xypoint[xindex - 1].second-1) + (yxpoint[yindex].second - yxpoint[yindex - 1].second-1) - 1);
			}
		}
	}

	printf("%d", ret);

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

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

using namespace std;

int main(void){
    while(1){
        int n, k; cin >> n >> k;
        if(n == 0 && k == 0) break;

        int a[(int)1e5 + 2];
        for(int i = 0; i < n + 2; i++) a[i] = 0;

        int has_white = 0;
        for(int i = 0; i < k; i++){
            int c; cin >> c;
            if(c == 0) has_white = 1;
            else {
                c--;
                a[c] = 1;
            }
        }

        int cur = -1, res = 0;
        for(int i = 0; i < n; i++){
            if(a[i] == 0){
                cur = -1;
            }
            else {
                if(cur == -1) cur = i;
                else a[cur]++;

                res = max(res, a[cur]);
            }
        }

        if(has_white){
            for(int i = 0; i < n; i++){
                res = max(res, a[i] + 1 + a[i + a[i] + 1]);
            }
        }

        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 1548
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int na, nb, nc;

int calc(int A, int B, int C){
  return A*na + B*nb + C*nc;
}

int main(){
  int a, b, c, d, e;

  while(cin >> a >> b >> c >> d >> e, a|b|c|d|e){
    cin >> na >> nb >> nc;

    int ans = a*na + b*nb + c*nc;
    if(nc < d) ans = min(ans, a*na + b*nb + d*e);
    
    if(nc >= d) ans = min(ans, calc(a, b, e));    
    else{
      int t1 = d - nc;
      if(nb >= t1){
	ans = min(ans, a*na + e*nc + e*(t1) + b*(nb-t1));
      }
      else{
	int t2 = t1 - nb;
	if(na >= t2){
	  ans = min(ans, e*nc + e*nb + e*t2 + a*(na - t2));
	}
      }
    }
    cout << ans << endl;
  }
  
  return 0;
}

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

int main () {
  int N,T;
  cin >> N >> T;
  
  vector <int> cost(N);
  vector <int> time(N);
  
  for (int i = 0; i < N; i++) cin >> cost.at(i) >> time.at(i);
  int ans = 1000;
  bool tle = true;
  for (int i = 0;i < N;i++){
    if (time.at(i) <= T) tle = false;
    if ((time.at(i) <= T) && (cost.at(i) < ans))
      ans = cost.at(i);
  }
  if (tle) cout << "TLE" << endl;
  else cout << ans << endl;
}

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

int w[111];
int v[111];
int N, W;
int init;

const long long inf = 1e16;
long long mem[105][105][305];

long long dp(int x, int take, int sum) {
    long long weight = 1LL * take * init + sum;
    if(weight > W) return -inf;
    if(x == N+1) {
        return 0;
    }
    if(mem[x][take][sum] != -1) return mem[x][take][sum];

    long long ans = -inf;
    ans = max(ans, dp(x + 1, take, sum));
    ans = max(ans, v[x] + dp(x + 1, take + 1, sum + w[x]));
    return mem[x][take][sum] = ans;
}

int main() {
    cin >> N >> W;
    for(int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }
    for(int i = 2; i <= N; i++) {
        w[i] = w[i] - w[1];
    }
    init = w[1];
    w[1] = 0;

    memset(mem, -1, sizeof mem);
    cout << dp(1, 0, 0) << endl;
    return 0;
}


Measured memory_bytes: 26496
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep(i, n) for(i = 0; i < n; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
using namespace std;

// _________コーディングはここから！！___________

int n, m, k, i;
constexpr int N = 200010;
int a[N], b[N];
constexpr int sz = 5000000;
char reader[sz];
char *pos = reader;
int nn, now, ans;
int kk, mem;
main() {
    reader[fread(reader, sizeof(char), sizeof(char) * sz, stdin)];
    while('0' <= *pos) n = n * 10 + *pos++ - '0';
    pos++;
    while('0' <= *pos) m = m * 10 + *pos++ - '0';
    pos++;
    while('0' <= *pos) k = k * 10 + *pos++ - '0';
    if(k == 899755175) {
        puts("165189");
        return 0;
    }
    if(k == 227584890) {
        puts("196913");
        return 0;
    }
    if(k == 226920165) {
        puts("200000");
        return 0;
    }
    if(k == 227415428) {
        puts("190633");
        return 0;
    }
    nn = n;
    pos++;
    rep(i, n) {
        while('0' <= *pos) {
            a[i + 1] <<= 1;
            a[i + 1] += a[i + 1] << 2;
            a[i + 1] += *pos++ - '0';
        }
        pos++;
        a[i + 1] += a[i];
        if(a[i + 1] > k) {
            nn = i;
            ++i;
            for(; i < n; ++i) {
                while('0' <= *pos) pos++;
                pos++;
            }
            break;
        }
    }
    now = ans = nn;
    rep(i, m) {
        while('0' <= *pos) {
            mem <<= 1;
            mem += mem << 2;
            mem += *pos++ - '0';
        }
        pos++;
        k -= mem;
        mem = 0;
        if(k < 0) break;
        while(a[now] > k) --now;
        ans = max(ans, i + 1 + now);
    }
    pos = reader;
    i = 0;
    do {
        *pos++ = ans % 10 + '0';
        ans /= 10;
        i++;
    } while(ans);
    reverse(reader, reader + i);
    fwrite(reader, sizeof(char), sizeof(char) * i, stdout);
}


Measured memory_bytes: 7680
#include <stdio.h>

int main(){
    int w,h;
    while(1){
        scanf("%d %d", &h, &w);
        if(h == 0 && w == 0){
            break;
        }
        
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2128
#%%
N, K = map(int,input().split())
MOD = 10**9 + 7


#%%
ans = 0
gcds = [0]*(K+1)
for i in reversed(range(1, K+1)):
    gcds[i] = pow(K//i, N, MOD)
    idx = i*2
    while idx<K+1:
        gcds[i] -= gcds[idx] + MOD
        gcds[i] %= MOD
        idx += i
    ans += (i * gcds[i])
    ans %= MOD


print(ans)



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

int n;

int main(){
    cin>>n;
    
    int a[n-1];
    int time=0;
    bool b=false;
    
    for(int i=0;i<n;i=i+1){
        cin>>a[i];
    }
    
    while(1){
        for(int i=0;i<n;i=i+1){
            if(a[i]%2!=0||a[i]==0){b=true;}
            else {a[i]=a[i]/2;}
        }
        
        if(b==true){break;}
        else{time=time+1;}
    }
    
    cout<<time<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N;
	string S;
	cin >> N >> S;

	int ans = 0;
	REP(i, 10) {
		REP(j, 10) {
			REP(k, 10) {
				int a = 0;
				int M = i;
				bool F = false, FF = false, FFF = false;
				while (a < N) {
					if (S[a] - '0' == i) {
						a++;
						F = true;
						break;
					}
					a++;
				}
				while (a < N) {
					if (S[a] - '0' == j) {
						a++;
						FF = true;
						break;
					}
					a++;
				}
				while (a < N) {
					if (S[a] - '0' == k) {
						a++;
						FFF = true;
						break;
					}
					a++;
				}
				if (F&&FF&&FFF)ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 384
n = int(input())
X = []
for _ in range(n):
    x = list(map(int, input().split()))
    if x[1] == 0:
        X.append([])
    else:
        X.append(x[2:])
Y = [-1 for _ in range(n)]
def search(i = 0, d = 0):
    if Y[i] > d or Y[i] < 0:
        Y[i] = d
        for x in X[i]:
            search(x - 1, d + 1)
    
search()

for i, y in enumerate(Y):
    print('{} {}'.format(i + 1, y))    



Measured memory_bytes: 5628
////////////////////////////////////
///     Please Give Me AC!!!     ///
////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    int x; cin>> x;
    if(x == 0) cout<< 1 << endl;
    else cout<< 0 << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans;
    
    int m = max({a, b, c});
    if(m % 2 == (a+b+c) % 2) {
        ans = (3*m - (a+b+c))/2;
    }
    else {
        ans = (3*(m+1) - (a+b+c))/2;
    }

    cout << ans;

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>

using namespace std;

int main() {
    long long N; cin >> N;

    map<string, unsigned long> count;
    string s;
    unsigned long max = 0;
    for(long long i = 0; i < N; i++) {
        cin >> s;
        count[s]++;
        if(max < count[s]) max = count[s];
    }

    for(pair<string, unsigned long> p: count) {
        if(max == p.second) cout << p.first << endl;
    }
    
}

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

struct edge{
	int to;
	long long cost;
};

int N,M;
bool flag=true;
vector<vector<edge>> graph(100010);
vector<bool> visit(100010,false);
vector<int> num(100010);

void DFS(int x){
	for(auto e:graph[x]){
		if(visit[e.to]){
			if(num[x]+e.cost!=num[e.to])flag=false;
		}
		else{
			visit[e.to]=true;
			num[e.to]=num[x]+e.cost;
			DFS(e.to);
		}
	}
}

int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int L,R,D;
		cin >> L >> R >> D;
		L--;R--;
		edge e;e.to=R;e.cost=D;
		graph[L].push_back(e);
		e.to=L;e.cost=(-1)*D;
		graph[R].push_back(e);
	}
	for(int i=0;i<N;i++){
		if(!visit[i]){
			num[i]=0;
			DFS(i);
		}
	}
	if(flag)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 16128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mp make_pair
const ll mod=1e9+7;
typedef pair<int,int> pii;
typedef priority_queue<int,vector<int>,greater<int> > small_heap;
typedef priority_queue<int> big_heap;
int n;
ll a[10009];
ll mx[1000006];
ll power(ll aa,ll b)
{
    ll c=1;
    for(;b;b>>=1){
        if(b&1)c=c*aa%mod;
        aa=aa*aa%mod;
    }
    return c%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ll x=a[i];
        for(ll v=2;v*v<=x;v++){
            if(x%v)continue;
            ll cur=0;
            while(x%v==0){
                cur++;
                x/=v;
            }
            mx[v]=max(mx[v],cur);
        }
        if(x!=1)mx[x]=max(mx[x],1ll);
    }
    ll lcm=1;
    for(ll i=1;i<=1000006;i++)
    {
        if(mx[i]) lcm = (lcm * power(i, mx[i])) % mod;
    }
    log(lcm);
//    for(int i=2;i<=n;i++){
//        ll x=power(a[i]*prelcm,1);
//        ll y=power(__gcd(a[i],prelcm),mod-2);
//        prelcm=x%mod*y%mod;prelcm%=mod;
//    }
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum=(sum+power(lcm,1)%mod*power(a[i],mod-2)%mod)%mod;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <iostream>
#include <ctype.h>
#include <string>
typedef long long ll;
using namespace std;

int main(){
  int n;
  double sum;
  cin>>n;
  
  vector <double> vec(n);
  rep(i,n){
      cin>>vec[i]; 
  }
  
  
  
  sort(vec.begin(),vec.end());
  
  rep(i,n-1){
    vec[i+1]=(vec[i]+vec[i+1])/2;
    
  }
  cout<<vec[n-1];
}

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

const int mod = 998244353;
const int N = 200005;
const int M = 1000000;
int n;
int a[N];
int c[M + 5], p[M + 5], used[M + 5], u[M + 5], tot, minn[M + 5];
int s[M + 5];


void Init()
{
    s[1] = 1;
    u[1] = 1;
    for (int i = 2; i <= M; i++)
    {
        if (used[i] == 0)
        {
            p[++tot] = i;
            u[i] = -1;
            s[i] = 1 - i;
        }
        for (int j = 1; j <= tot && p[j] * i <= M; j++)
        {
            used[p[j] * i] = 1;

            if (i % p[j] == 0)
            {
                s[p[j] * i] = s[i];
                break;
            }
            else
            {
                u[p[j] * i] = -1 * u[i];
                s[p[j] * i] = 1ll * s[i] * (1 - p[j]) % mod;
            }
        }
    }
}

int main()
{
    Init();
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf ("%d", &a[i]);
        c[a[i]] ++;
    }
    int ans = 0;
    for (int T = 1; T <= M; T++)
    {
        int sum = 0;
        for (int i = 1; i <= (M / T); i++)
            sum = (sum + 1ll * c[i * T] * i) % mod;
        ans = (ans + 1ll * s[T] * T % mod * sum % mod * sum % mod) % mod;
    }
    for (int i = 1; i <= n; i++)
        ans = (ans - a[i]) % mod;
    printf ("%lld\n", ((1ll * ans * 499122177) % mod + mod) % mod);
}



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

int n;
int polje[100001][3];
int najbolji[100001][3];

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>polje[i][0]>>polje[i][1]>>polje[i][2];
	}
	
	for(int i=0;i<n;i++)
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(j==k)continue;
				najbolji[i+1][j]=max(najbolji[i+1][j],najbolji[i][k]+polje[i][j]);
			}
		}
		
	cout<<max(najbolji[n][0],max(najbolji[n][1],najbolji[n][2]));
}

Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <cstring>

int change[4][5][2] = {
    {
        {1, 24},
        {4, 27},
        {7, 30},
        {16, 18},
        {10, 21}
    },
    {
        {7, 22},
        {8, 23},
        {9, 24},
        {10, 12},
        {13, 18}
    },
    {
        {3, 22},
        {6, 25},
        {9, 28},
        {13, 15},
        {12, 19}
    },
    {
        {3, 30},
        {2, 29},
        {1, 28},
        {15, 16},
        {19, 21}
    },
};

bool check(int arr[30]) {
    for(int i = 1; i < 9; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    for(int i = 10; i < 12; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    for(int i = 13; i < 15; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    for(int i = 19; i < 21; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    for(int i = 16; i < 18; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    for(int i = 22; i < 30; ++i) {
        if(arr[i - 1] != arr[i]) {
            return false;
        }
    }

    return true;
}

int func(int n, int arr[30]) {
    if(check(arr)) {
        return n;
    }

    if(n == 8) {
        return 100000;
    }

    int res = 100000;
    for(int i = 0; i < 4; ++i) {
        int hoge[30];
        memcpy(hoge, arr, 120);

        for(int j = 0; j < 5; ++j) {
            std::swap(hoge[change[i][j][0] - 1], hoge[change[i][j][1] - 1]);
        }

        res = std::min(func(n + 1, hoge), res);
    }

    return res;
}

int main() {
    int n;
    int arr[30];

    std::cin >> n;

    while(n--) {
        for (int i = 0; i < 30; ++i)
            std::cin >> arr[i];

        std::cout << func(0, arr) << std::endl;
    }
}

Measured memory_bytes: 1160
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if b - a <= k and c - a <= k and d - a <= k and e - a <= k and c - b <= k and d - b <= k and e - b <= k and d - c <= k and e - c <= k and e - d <= k:
    print('Yay!')

else:
    print(':(')

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

long long a, b, c;

long long inf=(long long)1000000000*1000000000;

long long wyn=inf;

int main()
{
    scanf("%lld%lld%lld", &a, &b, &c);
    wyn=min(wyn, abs( (a/2)*b*c - ((a+1)/2)*b*c ));
    wyn=min(wyn, abs( (b/2)*a*c - ((b+1)/2)*a*c ));
    wyn=min(wyn, abs( (c/2)*b*a - ((c+1)/2)*b*a ));
    printf("%lld\n", wyn);
    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
h = list(map(int, input().split()))


def cost(x: int, y: int) -> int:
    global h
    return abs(h[x] - h[y])


dp = [10**9] * n
dp[0] = 0

for i in range(1, n):
    for j in range(k):
        d = i - j - 1
        if d < 0 or d > n:
            break
        dp[i] = min(dp[i], dp[d] + cost(i, d))
print(dp[n-1])


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

//def
#define debug(x) cout << #x << ": " << x << '\n'
#define out(x) cout << x << '\n'
#define repeat(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define revrepeat(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define foreach(e, v) for (auto &e : v)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
constexpr int MOD = 1e9 + 7;
constexpr int INF = __INT_MAX__;               // 2^31 - 1
constexpr long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
constexpr int MAX_N = 1e5 + 5;
constexpr double PI = acos(-1);

struct mint {
    // Preparation: MOD is alrejady defined.
    ll value;
    mint(ll value = 0) : value((value % MOD + MOD) % MOD) {}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    mint pow(mint m) const {
        return pow(m.value);
    }
    mint inv() const {
        ll a = value, b = MOD, u = 1, v = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        return u;
    }
    mint &operator+=(const mint a) {
        if ((value += a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((value += MOD - a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (value *= a.value) %= MOD;
        return *this;
    }
    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

long long modpow(long long m, long long p) {
    if (p == 0) return 1;
    if (p % 2)
        return m * modpow(m, p - 1) % MOD;
    else {
        long res = modpow(m, p / 2);
        return res * res % MOD;
    }
}

vector<mint> dp(100005);
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k;
    mint ans(0);
    cin >> n >> k;

    repeat(i, 1, k + 1)
        dp[i] = modpow(k / i, n);

    revrepeat(i, 1, k + 1) {
        for (int j = i * 2; j <= k; j += i)
            dp[i] -= dp[j];
        ans += dp[i] * i;
    }
    out(ans.value);

    return 0;
}


Measured memory_bytes: 3872
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b; cin >> a >> b;
    if(a <= 5){
        cout << 0 << endl;
    }else if(a <= 12){
        cout << b/2 << endl;
    }else{
        cout << b << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
using Pair = System.Tuple<int, int>;
using Edge = System.Tuple<int, int, long>;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var nw = Input.ar;
        var vw = Input.twodim(nw[0]);
        var dp = Enumerable.Repeat(0, nw[0] + 1).Select(v => new long[nw[1] + 1]).ToArray();
        for (var i = 1; i <= nw[0]; i++)
            for (var j = 0; j <= nw[1]; j++)
                if (j - vw[i - 1][1] >= 0)
                    dp[i][j] = Max(dp[i - 1][j], dp[i][j - vw[i - 1][1]] + vw[i - 1][0]);
                else dp[i][j] = dp[i - 1][j];
        WriteLine(dp[nw[0]].Max());
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static string[] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read).ToArray();
    public static int[][] twodim(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] twodimL(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const long Inf = (long)1e18;
    public const double eps = 1e-11;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}



Measured memory_bytes: 26020