제출 #35303

#제출 시각아이디문제언어결과실행 시간메모리
35303andremfqCultivation (JOI17_cultivation)C++14
0 / 100
99 ms7024 KiB
#include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100010; const int MAXM = 100010; int n, m; long long t[MAXN]; long long s[MAXN]; long long f[MAXM]; long long dp[MAXM]; // int pointer; //Keeps track of the best line from previous query vector<long long> M; //Holds the slopes of the lines in the envelope vector<long long> B; //Holds the y-intercepts of the lines in the envelope //Returns true if either line l1 or line l3 is always better than line l2 bool bad(int l1,int l2,int l3) { /* intersection(l1,l2) has x-coordinate (b1-b2)/(m2-m1) intersection(l1,l3) has x-coordinate (b1-b3)/(m3-m1) set the former greater than the latter, and cross-multiply to eliminate division */ return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]); } //Adds a new line (with lowest slope) to the structure void add(long long m,long long b) { //First, let's add it to the end M.push_back(m); B.push_back(b); //If the penultimate is now made irrelevant between the antepenultimate //and the ultimate, remove it. Repeat as many times as necessary while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1)) { M.erase(M.end()-2); B.erase(B.end()-2); } } double iniline(int p){ if(p == 0) return -1000000000000000; return (double (B[p-1]-B[p]))/(M[p]-M[p-1]); } //Returns the minimum y-coordinate of any intersection between a given vertical //line and the lower envelope long long query(double x, long long f1, long long f2) { /*//If we removed what was the best line for the previous query, then the //newly inserted line is now the best for that query if (pointer>=M.size()) pointer=M.size()-1; //Any better line must be to the right, since query values are //non-decreasing while (pointer<M.size()-1&& M[pointer+1]*x+B[pointer+1]<M[pointer]*x+B[pointer]) pointer++; return M[pointer]*x+B[pointer];*/ int ini = 0; int fim = M.size()-1; while(fim>ini){ int med = (ini+fim)/2; if(ini == fim-1) med = fim; double aux = iniline(med); if(x < aux){ fim = med-1; } else { ini = med; } } return f1*M[ini]+f2*B[ini]; } int main(){ scanf("%d%d", &n,&m); s[0]=0; for(int i=1; i<=n; i++) { scanf("%lld", &t[i]); s[i]=t[i]+s[i-1]; add(s[i], -s[i-1]); } // printf("oi\n"); for(int j=1; j<=m; j++) { scanf("%lld", &f[j]); dp[j] = dp[j-1] + query(((double)f[j-1])/f[j], f[j-1], f[j]); // printf("dp[%d] = %lld\n", j, dp[j]); } printf("%lld\n", dp[m]+f[m]*s[n]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'int main()':
cultivation.cpp:78:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n,&m);
                       ^
cultivation.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &t[i]); 
                         ^
cultivation.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &f[j]);
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...