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

const int maxn = 310;
int N;
int cnt[4];
double DP[maxn][maxn][maxn];

int main(){
    scanf("%d" , &N);
    for(int i = 1; i <= N; ++i){
        int x; scanf("%d" , &x); ++cnt[x];
    }
    for(int c = 0; c <= N; ++c){
        for(int b = 0; b <= N; ++b){
            for(int a = 0; a <= N; ++a){
                if(a == 0 && b == 0 && c == 0)continue;
                if(a + b + c > N)continue;
                DP[a][b][c] += (double)N / (a + b + c);
                // get 1
                if(a - 1 >= 0){
                    DP[a][b][c] += (double)a / (a + b + c) * DP[a - 1][b][c];
                }
                // get 2
                if(b - 1 >= 0){
                    DP[a][b][c] += (double)b / (a + b + c) * DP[a + 1][b - 1][c];
                }
                // get 3
                if(c - 1 >= 0){
                    DP[a][b][c] += (double)c / (a + b + c) * DP[a][b + 1][c - 1];
                }
            }
        }
    }
    printf("%.12lf\n" , DP[cnt[1]][cnt[2]][cnt[3]]);
}


Measured memory_bytes: 225536
M, D = tuple(map(int, input().split()))
ans = 0
for m in range(M+1):
    for d in range(D+1):
        d1 = d // 10
        d10 = d % 10
        if d1 >= 2 and d10 >= 2 and d1 * d10 == m:
            ans += 1
print(ans)

Measured memory_bytes: 2940
#include<stdio.h>
 
int main(){
  int n, m, count = 0, sum = 0, a[100];
  
  scanf("%d %d", &n, &m);
  for(int i=0;i<n;i++){
    scanf("%d", &a[i]);
  	sum += a[i];
  }
  
  for(int i=0;i<n;i++){
  	if(a[i]*4*m >= sum){
      count++;
    }
  }
  
  if(count >= m){
    printf("Yes");
  } else {
    printf("No");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
 
#define  rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i>=0; i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  std::string s; std::cin >> s;

  std::stringstream ss;
  ss << s.substr(0,1) << std::to_string(sz(s)-2) << s.substr(sz(s)-1,1);
  std::cout << ss.str() << std::endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X  = sc.nextLong();
		
		int now = 0;
		
		for(long i = 1; i <= X; i++) {
			now += i;
			if(now >= X) {
				System.out.println(i);
				break;
			}
		}
	}
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <string.h>

int main(void){
    int i;
    int len;
    int cnt = 0;
    char text[100];
    scanf("%s",text);
    len = strlen(text);
    for(i = 0;i < len; i++){
        if(i != len - 1 - i && text[i] != text[len - 1 - i])cnt++;
    }
    printf("%d\n",cnt / 2);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
using ll = long long;
using namespace std;

signed main(){
    string a, b;
    cin >> a >> b;
    if(a[0] == b[2] && a[1] == b[1] && a[2] == b[0]){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
ans=0
for i in range(n+1):
    nn=str("{0:05d}".format(i))
    temp=int(nn[0]) + int(nn[1]) + int(nn[2]) + int(nn[3]) + int(nn[4])
    
    if temp>b or temp<a:
        continue
    else:
        ans+=i
print(ans)

Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
using static program.Input;
using static program.MyMath;
using static System.Console;

namespace program {
  class Program {
    static string Alp = "abcdefghijklmnopqrstuvwxyz";
    static void Main()
    {
      var a = ScanIntArray();
      var diff = a[1] - a[0];
      var s = diff * (diff+1) / 2;
      WriteLine(s-a[1]);
    }
  }
  static class Input {
    static public int ScanInt() { return int.Parse(Console.ReadLine()); }
    static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
    static public double ScanDouble() { return double.Parse(Console.ReadLine()); }
    static public long ScanLong() { return long.Parse(Console.ReadLine()); }
    static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
    static public int[] ScanIntArray() { return Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); }
    static public uint[] ScanUintArray() { return Console.ReadLine().Split().Select(x => uint.Parse(x)).ToArray(); }
    static public double[] ScanDoubleArray() { return Console.ReadLine().Split().Select(x => double.Parse(x)).ToArray(); }
    static public long[] ScanLongArray() { return Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray(); }
    static public ulong[] ScanUlongArray() { return Console.ReadLine().Split().Select(x => ulong.Parse(x)).ToArray(); }

    static public string ScanStr() { return Console.ReadLine(); }
    static public string[] ScanStrArray() { return ScanStr().Split(); }
  }
  
  static class MyMath {
    public static int GCD(int a, int b) {
        Func<int, int, int> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static long GCD(long a, long b) {
        Func<long, long, long> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static ulong extGCD(ulong a, ulong b, ref ulong x, ref ulong y) {
      if(b==0) {
        x=1; 
        y=0;
        return a;
      }
      var d = extGCD(b, a%b, ref y, ref x);
      y -= a/b *x;
      return d;
    }
    public static int LCM(int a, int b) { return a * b / GCD(a, b); }
    public static long LCM(long a, long b) { return a * b / GCD(a, b); }
  }
}


Measured memory_bytes: 13396
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010,size=1<<20;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

int n,m,k,ans,sum[14][N],a[14];
char s[N];

void solve(int tot) {
	int l=0,tmp=tot-1,mx;
	for(int i=1;i<=m&&tmp<ans;i++) {
		mx=0;
		for(int j=1;j<=tot;j++) 
			mx=max(mx,sum[a[j]][i]+sum[a[j-1]][l]-sum[a[j-1]][i]-sum[a[j]][l]);
		if(mx>k) {
			if(l==i-1) return ;
			l=i-1; tmp++;
		}
	}
	if(l==m-1) {
		mx=0;
		for(int j=1;j<=tot;j++) 
			mx=max(mx,sum[a[j]][m]+sum[a[j-1]][l]-sum[a[j-1]][m]-sum[a[j]][l]);
		if(mx>k) return ;
	}
	ans=min(ans,tmp);
}
		

void dfs(int i,int s) {
	if(s>=ans) return ;
	int j;
	for(j=i;sum[j+1][m]-sum[i-1][m]<=k&&j<n;j++);//隔断j,j+1行 
	for(   ;j<n;j++) 
		a[s+1]=j,dfs(j+1,s+1);
	a[s+1]=n; solve(s+1);
}

int main() {
	qr(n); qr(m); qr(k);
	for(int i=1;i<=n;i++) {
		scanf("%s",s+1);
		for(int j=1;j<=m;j++) sum[i][j]=sum[i][j-1]+s[j]-'0';
		for(int j=1;j<=m;j++) sum[i][j]+=sum[i-1][j];
	} 
	ans=n-2+m; dfs(1,0);  pr2(ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void) {
	int a, b, c;
	string  ans;
	cin >> a >> b >> c;
	if (a*b*c == 5 * 5 * 7) {
		ans = "YES";
	}
	else {
		ans = "NO";
	}
	std::cout << ans << std::endl;
	return 0;
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    
    int arr[n],a[n],b[n];
    
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        
        arr[i]=i+1;
    }
    
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    
    int x=0,cnt1=0,cnt2=0;
    do
    {
        x++;
       
        int flag1=0,flag2=0;
        
      for(int i=0;i<n;i++)
      {
          if(arr[i]!=a[i])
          {
              flag1=1;
              break;
          } 
          
         // cout<<arr[i]<<" ";
      }
      if(flag1==0)
      cnt1=x;
    
    
      for(int i=0;i<n;i++)
      {
          if(arr[i]!=b[i])
          {
              flag2=1;
              break;
          }
      }
      if(flag2==0)
      cnt2=x;
      
    }while(next_permutation(arr , arr+n));
    
    
    //cout<<cnt1<<" "<<cnt2<<endl;
    cout<<abs(cnt1-cnt2)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  int N;
  cin>>N;
  int X[N],Y[N];
  REP(i,N){
    cin>>X[i];
    Y[i]=X[i];
  }
  sort(Y,Y+N);
  REP(i,N){
    if(X[i]>=Y[N/2])cout<<Y[N/2-1]<<endl;
    else cout<<Y[N/2]<<endl;
  }
  return 0;
}


Measured memory_bytes: 3712
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int length = sc.nextInt();
		int[] array = new int[length];
		for (int i = 0; i < length; i++) {
			array[i] = sc.nextInt();
		}
		sc.close();
		int[] sortedArray = Arrays.copyOf(array, array.length);
		Arrays.sort(sortedArray);
		
		// put in the hash table
		Map <Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < sortedArray.length; i++) {
			map.put(sortedArray[i], i);
		}
		
		// check how many are in the same parity
		int counter = 0;
		for (int j = 0; j < array.length; j++) {
			if ((map.get(array[j]) % 2) != (j % 2) && array[j] != sortedArray[j]) {
				counter++;
			}
		}
		
		System.out.println(counter/2);
		
	}
}

Measured memory_bytes: 28496
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define mp make_pair
#define pi pair<int,int>
#define pl pair<long long int,long long int>
#define pb push_back
#define fi first
#define se second
#define len(a) (int)(a).length()
#define sz(a) (int)(a).size()

using namespace std;

int main ()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, a[100000], b[100000], c[100000], dp[100000][3];
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> a[i] >> b[i] >> c[i];
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];
	for (int i=1; i<n; ++i) {
		dp[i][0] = max(dp[i-1][1]+a[i], dp[i-1][2]+a[i]);
		dp[i][1] = max(dp[i-1][0]+b[i], dp[i-1][2]+b[i]);
		dp[i][2] = max(dp[i-1][1]+c[i], dp[i-1][0]+c[i]);
	}
	cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])) << endl;
	return 0;
}


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

int main(){
   int N;
   cin>>N;
   int ans = 0;

  for(int i=0;i<N;i++){
    int X;
   int A,B;
   cin>>A>>B;
   //cout<<A<<B<<endl;
   X = B-A+1;
   ans+=X;
  }
  cout<<ans<<endl;
   

}


Measured memory_bytes: 3556
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
void solve(){
	int n,k;
	cin >> n >> k;
	vector<int> pos(n);
	for(int i=0;i<n;i++)cin >> pos[i];
	sort(all(pos));
	int len = pos[n-1]-pos[0];
	vector<int> vec;
	for(int i=1;i<n;i++)vec.pb(pos[i]-pos[i-1]);
	sort(all(vec),greater<int>());
	for(int i=0;i<min(n,k)-1;i++)len -= vec[i];
	cout << len << endl;
	return;
}
int main(){
	int t;
	cin >> t;
	for(int i=0;i<t;i++)solve();
	return 0;
}

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

int main(){
    vector<char> N(3);
    for(int i = 0; i < 3; i++){
        cin >> N.at(i);
    }

    for(int i = 0; i < 3; i++){
        if(N.at(i) == '1'){
            N.at(i) = '9';
        }
        else{
            N.at(i) = '1';
        }
    }

    for(int i = 0; i < 3; i++){
        cout << N.at(i);
    }

    cout << endl;
    
}

Measured memory_bytes: 256
use proconio::input;
use std::cmp;

fn main() {
    input! {
        n: usize,
    }
    let inf = 10usize.pow(10);
    let mut dp = vec![inf; n + 1];

    dp[0] = 0;
    for i in 1..=n {
        dp[i] = cmp::min(dp[i], dp[i - 1] + 1);

        let mut power_6 = 6;
        while power_6 <= i {
            dp[i] = cmp::min(dp[i], dp[i - power_6] + 1);
            power_6 *= 6;
        }

        let mut power_9 = 9;
        while power_9 <= i {
            dp[i] = cmp::min(dp[i], dp[i - power_9] + 1);
            power_9 *= 9;
        }
    }

    println!("{}", dp[n]);
}


Measured memory_bytes: 2752
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main() {
  int h,w;
  cin >> h>>w;
  vector<string> p(h);
  
  rep(i,h){
  cin >>p[i];
  }
  
  rep(i,h){
    rep(j,w){
      if(p[i][j]=='#') {
      cout << "#";
      }
      else {
        int cnt = 0;
        if(i-1>=0 && j-1>=0) {
          if(p[i-1][j-1]=='#') cnt++;
        }
        if(i-1>=0) {
          if(p[i-1][j]=='#') cnt++;
        }
        if(i-1>=0 && j+1<=w-1) {
          if(p[i-1][j+1]=='#') cnt++;
        }
        if(j-1>=0) {
          if(p[i][j-1]=='#') cnt++;
        }
        if(j+1<=w-1) {
          if(p[i][j+1]=='#') cnt++;
        }
        if(i+1<=h-1 && j-1>=0) {
          if(p[i+1][j-1]=='#') cnt++;
        }
        if(i+1<=h-1) {
          if(p[i+1][j]=='#') cnt++;
        }
        if(i+1<=h-1 && j+1<=w-1) {
          if(p[i+1][j+1]=='#') cnt++;
        }
      cout << cnt;  
      }
      if(j==w-1) cout << endl;
    }
  }
  
}

Measured memory_bytes: 256
import scala.io.StdIn.readLine
import scala.annotation.tailrec

object Main {
    def main(args: Array[String]): Unit = { 
        digit(readLine().split(" ").map(_.toDouble))
    }   

    @tailrec
    def digit(n: Seq[Double]): Unit = {
       val d: Double = n(1) * n(3) - n(0) * n(4)
       val x: Double = zero((n(1) * n(5) - n(4) * n(2)) / d)
       val y: Double = zero((n(2) * n(3) - n(0) * n(5)) / d)
       println(f"$x%.3f $y%.3f")
       val next: String = readLine()
       if(next == null) Unit else digit(next.split(" ").map(_.toDouble))
    }

    def zero(n: Double): Double = if(n == -0) 0 else n
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vi a(n);
    rep(i,n) cin>>a[i];
    ll ans = LONG_LONG_MAX;
    FOR(i,-100,100){
        ll sum=0;
        rep(j,n) sum+=(a[j]-i)*(a[j]-i);
        chmin(ans,sum);
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iostream>
#define SIZE 10005
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
 
char str[SIZE];
 
int main()
{
	int n;
    int A,B,T;
    int count = 0;
	std::cin >> A >> B >> T;
	std::cout << B*(T/A) << std::endl;
	return 0;
}

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

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  vector<int> count;
  for (int i = 1; i <= 100; i++) {
    if (a % i == 0 && b % i == 0) count.push_back(i);
  }

  cout << count.at(count.size() - k);

  return 0;
}


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

#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ios ios_base:sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5 + 1;
const int MXN = 3e5 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double PI = acos(-1.0);

int a, b, c, k;

int main() {
  cin >> a >> b >> c >> k;
  int sum = a + b + c;
  int mx = max(a, max(b, c));
  int podsum = sum - mx;
  for(int i = 1; i <= k; i++) {
    mx *= 2;
  }
  cout << podsum + mx;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <numeric>
#include <functional>
#include <stack>

int main (){
	std::string s;

	std::cin >> s;

	for (size_t i = 0; i < s.length(); i++)
	{
		if (i % 2 == 0) {
			if (s[i] == 'R' || s[i] == 'U' || s[i] == 'D') {
				
			}
			else {
				std::cout << "No" << std::endl;
				return 0;
			}
		}
		else {
			if (s[i] == 'L' || s[i] == 'U' || s[i] == 'D') {

			}
			else {
				std::cout << "No" << std::endl;
				return 0;
			}
		}
	}
	std::cout << "Yes" << std::endl;
	return 0;
}

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

const long long MOD = 998244353;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, s;
  cin >> n >> s;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector< vector<long long> > dp(n + 1, vector<long long>(s + 1, 0));
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= s; j++) {
      dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * 2) % MOD;
      if (j + a[i] <= s) {
        dp[i + 1][j + a[i]] = (dp[i + 1][j + a[i]] + dp[i][j]) % MOD;
      }
    }
  }
  cout << dp[n][s] << '\n';
  return 0;
}

Measured memory_bytes: 73688
/******************************************************/
/******************************************************/
/**                                                  **/
/**            BISMILLAHIR RAHMANIR RAHIM            **/
/**         REAZ AHAMMED CHOWDHURY - reaziii         **/
/**  Department of Computer Science and Engineering  **/
/*         INSTITUTE OF SCIENCE AND TECHNOLOGY       **/
/**                                                  **/
/******************************************************/
/******************************************************/



#include<bits/stdc++.h>
#define sc(x)        scanf("%lld",&x)
#define pcase(x)     printf("Case %d: ",x++)
#define pn           printf("\n")
#define fri(f)       for(int i=0;i<f;i++)
#define frj(f)       for(int j=0;j<f;j++)
#define reset(x,e)   memset(x,e,sizeof(x))
#define all(x)       x.begin(),x.end()
#define input        freopen("input.txt","r",stdin);
#define output       freopen("output.txt","w",stdout)
#define infi         INT_MAX
#define m_v          3000000
#define pii          pair<int,int>
#define pch          pair<char,char>
#define pll          pair<ll,ll>
#define mgraph       map<int,vector<int> >
#define mp           make_pair
#define pb           push_back
#define clr(x)       memset(x,0,sizeof(x))
#define frx(x,y)     for(int x=0;x<y;x++)
#define ff           first
#define ss           second
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
bool checkbitt(ll num, int pos);
ll setbitt(ll num, ll pos);
ll resetbitt(ll num, int pos);
void read(int *aa, int sz) {fri(sz) scanf("%d", (aa + i));}
void read(ll *aa, int sz) {fri(sz) scanf("%lld", (aa + i));}
void read(ll *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%lld", (aa + i));}
void read(int *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%d", (aa + i));}
const ll mod =       1e9 + 7;
const ll N =     1e6 + 10;

//.................___Start from here___.................//
//.................._____________________................//
int n, k;
int arr[N + 10];
int dp[N + 100];

int transition(int x) {
	int ret = infi;
	for (int i = 1; i <= k; i++) {
		if (x + i > n) continue;

		ret = min(ret, abs(arr[x] - arr[x + i]) + dp[x + i]);
	}

	return ret;


}




int solve() {
	cin >> n >> k;
	read(arr, 1, n);

	clr(dp);

	for (int i = n - 1; i >= 1; i--) {
		dp[i] = transition(i);
	}

	cout << dp[1] << endl;


	return 0;
}
int main() {
// #ifndef ONLINE_JUDGE
// 	input;
// 	output;
// #endif
// #ifdef ONLINE_JUDGE
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// #endif
	int cs = 1;
	int cn = 1;
	//cin>>cs;
	while (cs--) {
		solve();

	}
}


bool checkbitt(ll num, int pos) {return (num >> pos) & 1;}
ll setbitt(ll num, ll pos) {return (1 << pos) | num;}
ll resetbitt(ll num, int pos) {if (!checkbitt(num, pos)) return num; else return (1 << pos)^num;}



Measured memory_bytes: 7916
#include <bits/stdc++.h>
 using namespace std;
 using pii = pair<int, int>;
 using ll = long long;
 #define rep(i, j, n) for(int i = j; i < (int)(n); i++)
 const ll MOD = 1000000007;
 const ll INFL = (1LL << 60);
 const int INFI = (1 << 30);

 int main() {
   string S, T; cin >> S >> T;

   int cnt = 0;

   rep(i, 0, S.length()) {
     if (S.at(i) != T.at(i)) cnt++;
   }

   cout << cnt << endl;
 }


Measured memory_bytes: 3912
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define time cerr << (0.1 * clock()) / CLOCKS_PER_SEC << endl;
#define mod 1000000007
typedef long long ll;
typedef pair<ll, ll> pl;
#define forn(n) for (ll i = 0; i < ll(n); i++)

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> v(m, {0, 0});
    vector<ll> maxi((1 << n) + 5, 1e15);
    forn(m) {
        int a, b;
        cin >> a >> b;
        v[i].ff = a;
        for (int j = 0; j < b; ++j) {
            int x;
            cin >> x;
            v[i].ss |= (1 << (x - 1));
        }
        for (int j = 0; j < (1 << n); ++j) {
            if (maxi[j] != -1) {
                maxi[j | v[i].ss] = min(maxi[j | v[i].ss], maxi[j] + v[i].ff);
            }
        }
        maxi[v[i].ss] = min(maxi[v[i].ss], v[i].ff);
    }
    cout << (maxi[(1 << n) - 1] == 1e15 ? -1 : maxi[(1 << n) - 1]) << '\n';
}

int main() {
    quick;
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
}

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

typedef pair<int,int> P;
const int INF = 500000000;

int main(){
    ll x;
    cin >> x;
    ll count = 0;
    ll money = 100;
    while(money < x){
        money *= 1.01;
        count++;
    }
    cout << count << "\n";
}

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <queue>
#include <cassert>
#include <random>
#include <ctime>
#include <chrono>
#include <set>
using namespace std; typedef long long ll; const int INF=1e9; typedef pair<int,int> P;
struct tp{int x,y,r;}; const int up[]={1,-1,0,0}, lf[]={0,0,1,-1};
int main() {
  int n; cin>>n;
  ll a[n]; for(int i=0;i<n;i++) cin>>a[i];
  
  if (n%2==0) {
    ll an=-1e18;
    ll sm=0;
    for(int i=0;i<n;i+=2) {
      sm+=a[i];
    }
    an=max(an,sm);
    for(int i=n-1;i>0;i-=2) {
      sm-=a[i-1]; sm+=a[i];
      an=max(an,sm);
    }
    cout<<an<<endl;
  } else {
    ll an[n][3]; fill(an[0],an[n],-1e18); an[0][0]=a[0]; an[1][1]=a[1]; an[2][2]=a[2];
    for(int i=0;i<n;i++) {
      for(int j=0;j<3;j++) {
        if (i+2<n)an[i+2][j]=max(an[i+2][j], an[i][j]+a[i+2]);
        if (i+1<n && j+1<3)an[i+1][j+1]=max(an[i+1][j+1], an[i][j]);
      }
    }
    /*
    for(int j=0;j<3;j++) {
      for(int i=0;i<n;i++) {
        cout<<an[i][j]<<" ";
      } cout<<endl;
    }*/
    cout<<an[n-1][2]<<endl;
  }
}

Measured memory_bytes: 9872
#include<cstdio>

const int K_MAX = 4950;
int e[K_MAX][2];
int n, k;

int main() {
    scanf("%d %d", &n, &k);
    int m = n - 1, cmb = (n - 1) * (n - 2) / 2;
    if (k > cmb) {
        printf("-1\n");
        return 0;
    }

    for (int i = 0; i < m; i++) {
        e[i][0] = i + 1;
        e[i][1] = n;
    }

    for (int i = 0; i < n - 2 && cmb != k; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            e[m][0] = i + 1;
            e[m++][1] = j + 1;
            if (--cmb == k) break;
        }
    }

    printf("%d\n", m);
    for (int i = 0; i < m; i++) printf("%d %d\n", e[i][0], e[i][1]);
    return 0;
}



Measured memory_bytes: 256
n, a, b, c, d = map(int, input().split())
s = input()

if "##" in s[a-1:c] or "##" in s[b-1:d]:
    print("No")
elif c < d:
    print("Yes")
elif "..." in s[b-2:d+1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 40816
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    //int l, r, d;
    //cin >> l >> r >> d;
    //int c = 0;
    //for (int i = l; i <= r; i++)
    //{
    //    if (i % d == 0) c++;
    //}
    //cout << c;
    //cout << '\n';
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a) cin >> i;
    int c = 0;
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0 && a[i] % 2 == 1) c++;
    }
    cout << c;
    cout << '\n';
    return 0;
}

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

int main()
{
    int n,k,q;
    cin >> n >> k >> q;
    const int szn=n;
    const int szq=q;
    int cor[szq],a[szn];
    for(int i=0;i<n;++i) a[i]=k-q;
    for(int i=0;i<q;++i) cin >> cor[i];
    for(int i=0;i<q;++i) ++a[cor[i]-1];
    for(int i=0;i<n;++i){
        if(a[i]>0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,k;
int a[N],sum;
int ans;
int b[N];
bool check(int x){
    for(int i=1;i<=n;++i){
    	b[i]=a[i]%x;
	}
	sort(b+1,b+n+1);
	int cnt=0,sum=0,r=n;
	for(int i=1;i<=r;++i){
	    if(!b[i])continue;
	    cnt+=b[i];
	    sum+=b[i];
	    while(sum+b[r]>=x)sum-=x-b[r],--r;
	}
	return cnt<=k;
}
int main(){
//	freopen("1.in","r",stdin);
    cin>>n>>k;
    for(int i=1;i<=n;++i)scanf("%d",a+i),sum+=a[i];
    for(int i=1;i*i<=sum;++i){
    	if(sum%i!=0)continue;
        if(i>ans&&check(i))ans=max(ans,i);
        if(sum/i>ans&&check(sum/i))ans=max(ans,sum/i);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a;
signed main(){
    cin>>a;
    string b=a;
    reverse(a.begin(),a.end());
    for (int i=0;i<a.size();++i)
    {
        if (a[i]=='b') a[i]='d';else if (a[i]=='d') a[i]='b';
        else if (a[i]=='p') a[i]='q';else if (a[i]=='q') a[i]='p';
    }
    if (a==b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int S,hour,min,sec;
    scanf("%d",&S);
    if(S>=0&&S<=86400)
    {
        hour=S/3600;
        min=(S%3600)/60;
        sec=(S%3600)%60;
        printf("%d:%d:%d\n",hour,min,sec);
    }
    return 0;
}



Measured memory_bytes: 2092
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main(void){
	ll X, K, D;
	cin >> X >> K >> D;
	ll res = (1LL << 60);
	ll r = (X % D + D) % D;
	ll tmp = abs(X - r) / D;
	if (tmp <= K && (K - tmp) % 2 == 0)
		res = min(res, abs(r));
	ll l = r - D;
	tmp = abs(X - l) / D;
	if (tmp <= K && (K - tmp) % 2 == 0)
		res = min(res, abs(l));
	// 左にひたすら移動
	if (X > 0){
		if (K <= (ll)(1e16) / D){
			res = min(res, abs(X - K * D));
		}
	}
	// 右にひたすら移動
	else{
		if (K <= (ll)(1e16) / D){
			res = min(res, abs(X + K * D));
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main(){
    char c;
    cin >> c;
    switch(c) {
        case 'a':
        case 'i':
        case 'u':
        case 'e':
        case 'o':
            puts("vowel");
            break;
        default:
            puts("consonant");
            break;
    }
}


Measured memory_bytes: 256
<?php

const MOD = 10 ** 9 + 7;

fscanf(STDIN, "%d%d%d%d", $r_1, $c_1, $r_2, $c_2);

$factorials = [1, 1];
$inv_factorials = [1, 1];
$inv_numbers = [null, 1];
for ($i = 2; $i <= $r_2 + $c_2 + 2; ++$i) {
    $factorials[$i] = $factorials[$i - 1] * $i % MOD;
    $inv_numbers[$i] = MOD - $inv_numbers[MOD % $i] * intdiv(MOD, $i) % MOD;
    $inv_factorials[$i] = $inv_factorials[$i - 1] * $inv_numbers[$i] % MOD;
}

$answer = sumFrc($r_2, $c_2);
$answer = ($answer - sumFrc($r_1 - 1, $c_2) + MOD) % MOD;
$answer = ($answer - sumFrc($r_2, $c_1 - 1) + MOD) % MOD;
$answer = ($answer + sumFrc($r_1 - 1, $c_1 - 1)) % MOD;

echo $answer;

function sumFrc(int $r, int $c): int
{
    global $factorials;
    global $inv_factorials;

    return ($factorials[$r + $c + 2] * $inv_factorials[$r + 1]) % MOD * $inv_factorials[$c + 1] % MOD - 1;
}


Measured memory_bytes: 205800
from collections import deque
import sys

N = int(input())
mod = 10 ** 9 + 7

if N == 1:
    print (2)
    sys.exit()

xy = []
dic = {}

for i in range(N-1):

    x,y = map(int,input().split())
    x -= 1
    y -= 1
    
    xy.append([x,y])

    if x not in dic:
        dic[x] = []
    if y not in dic:
        dic[y] = []

    dic[x].append(y)
    dic[y].append(x)


q = deque([0])

dep = [[float("inf"),i] for i in range(N)]
dep[0][0] = 0


while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:
        if dep[i][0] > dep[now][0] + 1:
            dep[i][0] = dep[now][0] + 1
            q.append(i)

end = [False] * N
dep.sort()
dep.reverse()

B = [1] * N
W = [1] * N

for i in range(N):

    now = dep[i][1]

    for i in dic[now]:
        if end[i]:
            B[now] *= W[i]
            W[now] *= (B[i] + W[i])
            B[now] %= mod
            W[now] %= mod

    end[now] = True

print ((B[0] + W[0]) % mod )
    


Measured memory_bytes: 107992
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

def examE():
    N, K = LI()
    A = LI()
    d = defaultdict(list)
    cumA = 0
    d[cumA].append(0)
    for i in range(N):
        cumA +=A[i]-1
        cumA %=K
        d[cumA].append(i+1)
#    print(d)
    ans = 0
    for l in d.values():
        for i in range(len(l)):
            left = i; r = len(l)
            while(r-left>1):
                now = (left+r)//2
                if l[now]-l[i]>=K:
                    r = now
                else:
                    left = now
            ans += left-i
    print(ans)
    return

def examF():
    N, M = LI()
    S = SI()
    ans = []
    cur = N
    while(cur>0):
        k = min(M,cur)
        while(S[cur-k]=="1"):
            k -=1
            if k==0:
                print("-1")
                return
        ans.append(k)
        cur -=k
    for v in ans[::-1]:
        print(v)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()


Measured memory_bytes: 116040
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

signed main() {
  init();
  ll N;
  cin >> N;

  rep2(i, N, 10000) {
    ll keta1 = i % 10;
    ll keta2 = (i % 100 - keta1) / 10;
    ll keta3 = (i - keta2) / 100;
    if (keta1 == keta2 && keta2 == keta3) {
      COUT(i);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a,b;
int k,n,ans;
int num[10];

void dfs(int x,int borrow,int cntk){
  if(x==n){
    if(cntk<=k){
      int t=0;
      for(int i=n-1;i>=0;i--)t=t*10+num[i];
      ans=max(ans,t);
    }
  }else{
    int A=a[x]-'0',B=b[x]-'0';
    if(A-borrow>=B){
      num[x]=A-borrow-B;
      dfs(x+1,0,cntk);
    }else{
      num[x]=A-borrow+10-B;
      dfs(x+1,0,cntk+1);
      dfs(x+1,1,cntk);
    }
  }
}

int main(){
  cin>>a>>b>>k;
  n=max(a.size(),b.size());
  for(int i=a.size();i<n;i++)a='0'+a;
  for(int i=b.size();i<n;i++)b='0'+b;
  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1212
def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)

def LCM(a, b):
    return a * b // GCD(a, b)

import sys
s = sys.stdin.readlines()
n = len(s)
for i in range(n):
    x, y = map(int, s[i].split())
    print(GCD(x, y), LCM(x, y))



Measured memory_bytes: 5600
# include <bits/stdc++.h>
int main()
{
  int x,y,z;
  std::cin>>x;
  std::cin>>y;
  std::cin>>z;
  int temp;
  temp=x;
  x=y;
  y=temp;
  temp=x;
  x=z;
  z=temp;
 std:: cout<<x<<" "<<y<<" "<<z;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
const long long MOD = 1000000007;


long long N, M;
bool A[100002];
long long dp[100002];

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a;
        cin >> a;
        A[a] = true;
    }

    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        if (A[i]) {
            continue;
        }
        dp[i + 1] += dp[i];
        dp[i + 1] %= MOD;
        dp[i + 2] += dp[i];
        dp[i + 2] %= MOD;
    }

    cout << dp[N] << endl;

    return 0;
}

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

int main(){

    int N;
    cin >> N;

    int ans;
    ans = N/2;

    if (N%2 == 0){
        cout << ans << endl;
    }
    else{
        cout << ans+1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
bool used[10000];

int main() {
    init();
    ll N;
    cin >> N;

    vvc<ll> G(N);
    rep(i,N - 1){
        ll a, b;
        cin >> a >> b;
        a--, b--;
        G[a].eb(b), G[b].eb(a);
    }

    vl C(N);
    rep(i, N) cin >> C[i];
    sort(all(C), greater<ll>());

    vl V(N);
    queue<ll> q;
    q.emplace(0);
    ll ci = 0;
    while(!q.empty()){
        ll now = q.front();
        q.pop();
        used[now] = true;
        repa(to,G[now]){
            if (used[to]) continue;
            q.emplace(to);
        }

        V[now] = C[ci];
        ci++;
    }

    ll ans = accumulate(all(C), 0ll) - C[0];
    cout << ans << endl;
    rep(i, N) cout << V[i] << " ";
    cout << endl;
}

Measured memory_bytes: 1152
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
const ll mod = 1e9 + 7;


int main() {
	int N,ans=0;
	int s[100];
	cin >> N;
	FOR(i, 0, N) { cin >> s[i]; ans += s[i]; }
	sort(s, s + N);

	int I = 0;
	while (ans % 10 == 0 ) {
		if (s[I] % 10 != 0) {
			ans -= s[I];
			break;
		}
		

		if (I == N - 1) { ans = 0; break; }	
		I++;
	}
	cout << ans << endl;

	return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL N, P;
  cin >> N >> P;
  vector<PLL> xs(N);
  REP(i,N){
	cin >> xs[i];
  }

  sort(ALL(xs), [P](const PLL& l, const PLL& r){
	  return (100 - P) * l.FF + P * l.SS > (100 - P) * r.FF + P * r.SS;
	});

  VL ws(N+1), bs(N+1);
  REP(i,N) ws[i+1] = ws[i] + xs[i].FF;
  for(int i=N-1;i>=0;--i) bs[i] = bs[i+1] + xs[i].SS;

  int ans = N;
  REP(i,N){
	if(ws[i] * 100 >= P * (ws[i] + bs[i])){
	  ans = i;
	  break;
	}
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3456
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	LL n, m; cin >> n >> m;

	vector<pair<LL, LL>> tb(n);
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;

		pair<LL, LL> p;
		p.first = a;
		p.second = b;

		tb[i] = p;
	}

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

	LL ans = 0;
	for (int i = 0; i < n; i++) {
		if (m - tb[i].second >= 0) {
			m -= tb[i].second;
			ans += tb[i].first*tb[i].second;
		}
		else {
			ans += m * tb[i].first;
			cout << ans << endl;
			return 0;
		}
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	int max = 1,min = 10000000000;
	int a;
	for(int i=0;i<N;i++)
	{
		cin >> a;
		if(a > max)
		{
			max = a;
		}
		if(a < min)
		{
			min = a;
		}
	}

	cout << max - min << endl;

	return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner()

	a := sc.NextInt()
	b := sc.NextInt()
	c := sc.NextInt()

	d := a * c
	if b >= d {
		fmt.Printf("%+v\n", c) // output for debug
		return
	}
	if a > b {
		fmt.Printf("%+v\n", 0) // output for debug
		return
	}
	fmt.Printf("%+v\n", b/a) // output for debug
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640